저녁 8시에 있었던 매치.. 음.. 상금매치여서그런지.. 열라 어려웠다.. 젱장!!!! ㅠ_ㅠ 두번연속 0점.. ㅠ_ㅠ;; 아.. 허무하다.. 근데 신기하게도 두번 다 rating은 올랐다.. 뭐 이래!!

챌만 잘했어도 순위권에 들 수 있었는데.. 망설이다가 결국 하나도 못했다.. ㅠ_ㅠ 한놈은 0점인데도불구하고 챌로만 325점 먹어서 상금탔다..

방 11등 전체 348등..

사용자 삽입 이미지



[250] StrongPrimePower
p^q (p는 prime, q는 1보다 큰 정수) 로 나타내어지는 수를 strong prime power라고 한다.. 주어진 수가 string prime power인지 구하고 맞다면 p와 q를 리턴하는 문제..

흠.. 그다지 어려운 문제가 아닌데.. 매치때 삽질했다.. n이 10^18 까지 나오므로 sqrt(n) 까지만 prime을 구하더라도 time limit이 난다.. 따라서 역발상으로 제곱근을 구해보자 생각했는데.. 어떻게 구해?? 하고 좌절하고 말았다.. 생각해보니.. pow 라는 매우좋은 함수가 있구나..!!!! -_-;;; 왜 생각을 못했지..;;;;

매치 에디토리얼에 있는 코드를 내 취향대로 대략 수정했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8
  9 int is_prime(int u)
 10 {
 11     int i;
 12     if (u <= 1)
 13         return 0;
 14     for (i = 2; i * i <= u; i++) {
 15         if (u % i == 0)
 16             return 0;
 17     }
 18     return 1;
 19 }
 20
 21 class StrongPrimePower {
 22 public:
 23
 24 vector<int> baseAndExponent(string N)
 25 {
 26     int p, q, i;
 27     long long n, x;
 28     double temp;
 29     vector<int> res;
 30
 31     sscanf(N.c_str(), "%lld", &n);
 32     for (q = 2; q <= 64; q++) {
 33         temp = pow(n, 1.0 / (double)q);
 34         p = (int)(temp + 0.00000001);
 35         if (!is_prime(p))
 36             continue;
 37         x = 1;
 38         for (i = 0; i < q; i++) {
 39             x *= p;
 40         }
 41         if (x == n) {
 42             res.push_back(p);
 43             res.push_back(q);
 44             break;
 45         }
 46     }
 47     return res;
 48 }
 49
 50 };




[500] ReversalChain



to be updated..




[1000] CollectingBonuses



to be updated..

'Problem Solving > TopCoder logs' 카테고리의 다른 글

TopCoder SRM 407 Div 1  (2) 2008.06.28
TopCoder SRM 405 Div 1  (2) 2008.06.15
TopCoder SRM 404 Div 1  (2) 2008.06.06
TopCoder SRM 402 Div 1  (0) 2008.05.25
TopCoder SRM 401 Div1  (2) 2008.05.07
리눅스에서 탑코더하기..  (0) 2008.05.01
TopCoder SRM 399 Div 1  (0) 2008.04.25
TopCoder SRM 398 Div1  (0) 2008.04.16
TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
SRM 395 Div1  (0) 2008.04.09

to Top