DIV1 250pt
题意：给定一个正整数n(n <= 10^18)，如果n = p^q，其中p为质数，q > 1，则返回vector<int> ans = {p, q}，否则返回ans = {}。
解法：首先，看到题的第一想法是，枚举p。而由于n的范围太大，O(10^9)的复杂度不能接受。又想到，如果题目的限制为q > 2，那么枚举的复杂度就降到了O(10^6)，可以接受了。故得到算法，特判n可不可以表示成p ^ 2的形式(注意判定p是不是质数)，然后再从1到10^6枚举看n能不能表示成p^q，其中q > 2。这样，问题能够得到解决，但是编码复杂度比较高，最后我写出来只拿到了160+分。
然后看了题解，枚举q...因为10^18 < 2^60，所以q的范围小于60。然后枚举就行了。注意三点，一、枚举的方法可以直接用pow来对n开方，也可以二分，前者会涉及浮点数但是好写。二、枚举的过程中算多少次方不需要快速幂，直接算容易写而且时间复杂度够。三、计算过程中要注意会不会爆long long，如果快爆long long直接返回-1或者0。
tag:math
解法一：
1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "StrongPrimePower.cpp" 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #include 26 #include 27 #include 28 #include 29 #include 30 #include 31 #include
VI; 47 typedef vector
VS; 48 typedef vector VD; 49 typedef pair pii; 50 typedef long long int64; 51 52 const double eps = 1e-8; 53 const double PI = atan(1.0)*4; 54 const int maxint = 2139062143; 55 const int maxx = 1000005; 56 57 int all; 58 bool vis[maxx]; 59 int prm[maxx]; 60 61 void sieve(int n) 62 { 63 int m = (int)sqrt(n+0.5); 64 CLR (vis); vis[0] = vis[1] = 1; 65 for (int64 i = 2; i <= m; ++ i) if (!vis[i]) 66 for (int64 j = i*i; j <= n; j += i) vis[j] = 1; 67 68 } 69 70 int primes(int n) 71 { 72 sieve(n); 73 int ret = 0; 74 for (int i = 2; i <= n; ++ i) 75 if (!vis[i]) prm[ret++] = i; 76 return ret; 77 78 } 79 80 bool ok(int64 n) 81 { 82 if (n <= 1000000) return (!vis[n]); 83 84 for (int i = 0; i < all; ++ i) 85 if ((n % prm[i]) == 0){ 86 return 0; 87 } 88 return 1; 89 } 90 91 int gao1(int64 n) 92 { 93 int64 m = (int64)sqrt(n + 0.5); 94 if (m*m != n) return -1; 95 96 if (ok(m)) return m; 97 return -1; 98 } 99 100 pii gao2(int64 n)101 {102 int ret;103 pii tmp;104 for (int i = 0; i < all; ++ i) if ((n % prm[i]) == 0){105 ret = 0;106 while ((n % prm[i]) == 0) {107 ++ ret;108 n /= prm[i];109 }110 if (ret > 1 && n == 1){111 tmp.first = prm[i];112 tmp.second = ret;113 return tmp;114 }115 else{116 tmp.first = -1;117 return tmp;118 }119 }120 tmp.first = -1;121 return tmp;122 }123 124 int64 gao(string n)125 {126 int64 ret = 0;127 for (int i = 0; i < n.size(); ++ i)128 ret = ret * 10 + n[i] - '0';129 return ret;130 }131 132 class StrongPrimePower133 {134 public:135 vector baseAndExponent(string N){136 all = primes(1000000);137 int64 n = gao(N);138 139 int64 tmp = gao1(n);140 vector ans;141 ans.clear();142 if (tmp != -1){143 ans.PB ((int)tmp); ans.PB (2);144 return ans;145 }146 pii t = gao2(n);147 if (t.first != -1){148 ans.PB (t.first); ans.PB (t.second);149 return ans;150 }151 return ans;152 }153 154 // BEGIN CUT HERE155 public:156 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }157 private:158 template string print_array(const vector &V) { ostringstream os; os << "{ "; for (typename vector ::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }159 void verify_case(int Case, const vector &Expected, const vector &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }160 void test_case_0() { string Arg0 = "27"; int Arr1[] = { 3, 3 }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, baseAndExponent(Arg0)); }161 void test_case_1() { string Arg0 = "10"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, baseAndExponent(Arg0)); }162 void test_case_2() { string Arg0 = "7"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, baseAndExponent(Arg0)); }163 void test_case_3() { string Arg0 = "1296"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, baseAndExponent(Arg0)); }164 void test_case_4() { string Arg0 = "576460752303423488"; int Arr1[] = { 2, 59 }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(4, Arg1, baseAndExponent(Arg0)); }165 void test_case_5() { string Arg0 = "999999874000003969"; int Arr1[] = { 999999937, 2 }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(5, Arg1, baseAndExponent(Arg0)); }166 167 // END CUT HERE168 169 };170 171 // BEGIN CUT HERE172 int main()173 {174 // freopen( "a.out" , "w" , stdout ); 175 StrongPrimePower ___test;176 ___test.run_test(-1);177 return 0;178 }179 // END CUT HERE View Code 1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "StrongPrimePower.cpp" 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #include 26 #include 27 #include 28 #include 29 #include 30 #include 31 #include
VI; 47 typedef vector
VS; 48 typedef vector VD; 49 typedef pair pii; 50 typedef long long int64; 51 52 const double eps = 1e-8; 53 const double PI = atan(1.0)*4; 54 const int maxint = 2139062143; 55 56 int64 gao(string n) 57 { 58 int64 ret = 0; 59 for (int i = 0; i < n.size(); ++ i) 60 ret = ret * 10 + n[i] - '0'; 61 return ret; 62 } 63 64 int64 mypow(int64 p, int64 n) 65 { 66 unsigned long long ret = 1; 67 for (int i = 0; i < n; ++ i){ 68 ret *= p; 69 if (ret > 1e18) return -1; 70 } 71 return ret; 72 } 73 74 bool ok(int y) 75 { 76 for (int64 i = 2; i*i <= y; ++ i) 77 if (y % i == 0) return 0; 78 return 1; 79 } 80 81 int gao(int64 n, int num) 82 { 83 int x = (int)pow(n, 1.0 / (double)num), y = -1; 84 for (int i = -1; i < 2; ++ i) 85 if (mypow(x+i,num) == n && ok(x+i)) y = x + i; 86 return y; 87 } 88 89 class StrongPrimePower 90 { 91 public: 92 vector baseAndExponent(string N){ 93 int64 n = gao(N); 94 VI ret; ret.clear(); 95 pii ans; 96 for (int i = 2; i < 61; ++ i){ 97 int tmp = gao(n, i); 98 if (tmp == -1) continue; 99 ret.PB (tmp); ret.PB (i);100 }101 return ret;102 }103 104 // BEGIN CUT HERE105 public:106 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }107 //void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}108 private:109 template string print_array(const vector &V) { ostringstream os; os << "{ "; for (typename vector ::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }110 void verify_case(int Case, const vector &Expected, const vector &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }111 void test_case_0() { string Arg0 = "639558602475808609"; int Arr1[] = {}; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, baseAndExponent(Arg0)); }112 void test_case_1() { string Arg0 = "10"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, baseAndExponent(Arg0)); }113 void test_case_2() { string Arg0 = "7"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, baseAndExponent(Arg0)); }114 void test_case_3() { string Arg0 = "1296"; int Arr1[] = { }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, baseAndExponent(Arg0)); }115 void test_case_4() { string Arg0 = "576460752303423488"; int Arr1[] = { 2, 59 }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(4, Arg1, baseAndExponent(Arg0)); }116 void test_case_5() { string Arg0 = "999999874000003969"; int Arr1[] = { 999999937, 2 }; vector Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(5, Arg1, baseAndExponent(Arg0)); }117 118 // END CUT HERE119 120 };121 122 // BEGIN CUT HERE123 int main()124 {125 // freopen( "a.out" , "w" , stdout ); 126 StrongPrimePower ___test;127 ___test.run_test(-1);128 return 0;129 }130 // END CUT HERE