Artifact 8c5bdf5260c7702442fe6f343523ddcfb4cda739:
0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6f 6d 70 ..#include <comp
00d0: 6c 65 78 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c lex>..#include <
00e0: 71 75 65 75 65 3e 0d 0a 23 69 6e 63 6c 75 64 65 queue>..#include
00f0: 20 3c 73 74 61 63 6b 3e 0d 0a 23 69 6e 63 6c 75 <stack>..#inclu
0100: 64 65 20 3c 63 6d 61 74 68 3e 0d 0a 23 69 6e 63 de <cmath>..#inc
0110: 6c 75 64 65 20 3c 63 61 73 73 65 72 74 3e 0d 0a lude <cassert>..
0120: 75 73 69 6e 67 20 6e 61 6d 65 73 70 61 63 65 20 using namespace
0130: 73 74 64 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f std;..typedef lo
0140: 6e 67 20 6c 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 63 ng long LL;....c
0150: 6c 61 73 73 20 53 74 72 6f 6e 67 50 72 69 6d 65 lass StrongPrime
0160: 50 6f 77 65 72 0d 0a 7b 0d 0a 70 75 62 6c 69 63 Power..{..public
0170: 3a 0d 0a 09 76 65 63 74 6f 72 20 3c 69 6e 74 3e :...vector <int>
0180: 20 62 61 73 65 41 6e 64 45 78 70 6f 6e 65 6e 74 baseAndExponent
0190: 28 73 74 72 69 6e 67 20 6e 29 20 0d 0a 09 7b 0d (string n) ...{.
01a0: 0a 09 09 4c 4c 20 4e 3b 0d 0a 09 09 73 74 72 69 ...LL N;....stri
01b0: 6e 67 73 74 72 65 61 6d 28 6e 29 20 3e 3e 20 4e ngstream(n) >> N
01c0: 3b 0d 0a 0d 0a 09 09 4c 4c 20 73 4e 20 3d 20 28 ;......LL sN = (
01d0: 4c 4c 29 20 73 71 72 74 28 20 28 64 6f 75 62 6c LL) sqrt( (doubl
01e0: 65 29 4e 20 29 3b 0d 0a 09 09 69 66 28 20 73 4e e)N );....if( sN
01f0: 2a 73 4e 20 3d 3d 20 4e 20 26 26 20 69 73 50 72 *sN == N && isPr
0200: 69 6d 65 28 73 4e 29 20 29 20 7b 0d 0a 09 09 09 ime(sN) ) {.....
0210: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 61 6e 73 3b vector<int> ans;
0220: 0d 0a 09 09 09 61 6e 73 2e 70 75 73 68 5f 62 61 .....ans.push_ba
0230: 63 6b 28 73 4e 29 3b 0d 0a 09 09 09 61 6e 73 2e ck(sN);.....ans.
0240: 70 75 73 68 5f 62 61 63 6b 28 32 29 3b 0d 0a 09 push_back(2);...
0250: 09 09 72 65 74 75 72 6e 20 61 6e 73 3b 0d 0a 09 ..return ans;...
0260: 09 7d 0d 0a 09 09 69 66 28 20 28 73 4e 2b 31 29 .}....if( (sN+1)
0270: 2a 28 73 4e 2b 31 29 20 3d 3d 20 4e 20 26 26 20 *(sN+1) == N &&
0280: 69 73 50 72 69 6d 65 28 73 4e 2b 31 29 20 29 20 isPrime(sN+1) )
0290: 7b 0d 0a 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 {.....vector<int
02a0: 3e 20 61 6e 73 3b 0d 0a 09 09 09 61 6e 73 2e 70 > ans;.....ans.p
02b0: 75 73 68 5f 62 61 63 6b 28 73 4e 2b 31 29 3b 0d ush_back(sN+1);.
02c0: 0a 09 09 09 61 6e 73 2e 70 75 73 68 5f 62 61 63 ....ans.push_bac
02d0: 6b 28 32 29 3b 0d 0a 09 09 09 72 65 74 75 72 6e k(2);.....return
02e0: 20 61 6e 73 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 ans;....}......
02f0: 66 6f 72 28 4c 4c 20 70 3d 32 3b 20 70 2a 70 2a for(LL p=2; p*p*
0300: 70 3c 3d 4e 3b 20 2b 2b 70 29 0d 0a 09 09 09 69 p<=N; ++p).....i
0310: 66 28 20 4e 25 70 3d 3d 30 20 29 20 7b 0d 0a 09 f( N%p==0 ) {...
0320: 09 09 09 4c 4c 20 71 3d 30 3b 0d 0a 09 09 09 09 ...LL q=0;......
0330: 77 68 69 6c 65 28 4e 25 70 3d 3d 30 29 0d 0a 09 while(N%p==0)...
0340: 09 09 09 09 4e 20 2f 3d 20 70 2c 20 2b 2b 71 3b ....N /= p, ++q;
0350: 0d 0a 09 09 09 09 69 66 28 20 4e 3d 3d 31 20 29 ......if( N==1 )
0360: 20 7b 0d 0a 09 09 09 09 09 76 65 63 74 6f 72 3c {.......vector<
0370: 69 6e 74 3e 20 61 6e 73 3b 0d 0a 09 09 09 09 09 int> ans;.......
0380: 61 6e 73 2e 70 75 73 68 5f 62 61 63 6b 28 70 29 ans.push_back(p)
0390: 3b 0d 0a 09 09 09 09 09 61 6e 73 2e 70 75 73 68 ;.......ans.push
03a0: 5f 62 61 63 6b 28 71 29 3b 0d 0a 09 09 09 09 09 _back(q);.......
03b0: 72 65 74 75 72 6e 20 61 6e 73 3b 0d 0a 09 09 09 return ans;.....
03c0: 09 7d 0d 0a 09 09 09 09 62 72 65 61 6b 3b 0d 0a .}......break;..
03d0: 09 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 76 ...}....return v
03e0: 65 63 74 6f 72 3c 69 6e 74 3e 28 29 3b 0d 0a 09 ector<int>();...
03f0: 7d 0d 0a 0d 0a 09 62 6f 6f 6c 20 69 73 50 72 69 }.....bool isPri
0400: 6d 65 28 4c 4c 20 4e 29 20 7b 0d 0a 09 09 66 6f me(LL N) {....fo
0410: 72 28 4c 4c 20 70 3d 32 3b 20 70 2a 70 3c 3d 4e r(LL p=2; p*p<=N
0420: 3b 20 2b 2b 70 29 0d 0a 09 09 09 69 66 28 4e 25 ; ++p).....if(N%
0430: 70 3d 3d 30 29 0d 0a 09 09 09 09 72 65 74 75 72 p==0)......retur
0440: 6e 20 66 61 6c 73 65 3b 0d 0a 09 09 72 65 74 75 n false;....retu
0450: 72 6e 20 74 72 75 65 3b 0d 0a 09 7d 0d 0a 7d 3b rn true;...}..};
0460: 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 ....// BEGIN CUT
0470: 20 48 45 52 45 0d 0a 74 65 6d 70 6c 61 74 65 20 HERE..template
0480: 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 73 74 72 <typename T> str
0490: 69 6e 67 20 70 72 69 6e 74 5f 61 72 72 61 79 28 ing print_array(
04a0: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 20 const vector<T>
04b0: 26 56 29 20 7b 20 6f 73 74 72 69 6e 67 73 74 72 &V) { ostringstr
04c0: 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 7b eam os; os << "{
04d0: 20 22 3b 20 66 6f 72 20 28 74 79 70 65 6e 61 6d "; for (typenam
04e0: 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e e vector<T>::con
04f0: 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 65 72 st_iterator iter
0500: 20 3d 20 56 2e 62 65 67 69 6e 28 29 3b 20 69 74 = V.begin(); it
0510: 65 72 20 21 3d 20 56 2e 65 6e 64 28 29 3b 20 2b er != V.end(); +
0520: 2b 69 74 65 72 29 20 6f 73 20 3c 3c 20 27 5c 22 +iter) os << '\"
0530: 27 20 3c 3c 20 2a 69 74 65 72 20 3c 3c 20 22 5c ' << *iter << "\
0540: 22 2c 22 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b ","; os << " }";
0550: 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 29 return os.str()
0560: 3b 20 7d 0d 0a 69 6e 74 20 76 65 72 69 66 79 5f ; }..int verify_
0570: 63 61 73 65 28 63 6f 6e 73 74 20 76 65 63 74 6f case(const vecto
0580: 72 20 3c 69 6e 74 3e 20 26 45 78 70 65 63 74 65 r <int> &Expecte
0590: 64 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 20 d, const vector
05a0: 3c 69 6e 74 3e 20 26 52 65 63 65 69 76 65 64 29 <int> &Received)
05b0: 20 7b 20 69 66 20 28 45 78 70 65 63 74 65 64 20 { if (Expected
05c0: 3d 3d 20 52 65 63 65 69 76 65 64 29 20 63 65 72 == Received) cer
05d0: 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c r << "PASSED" <<
05e0: 20 65 6e 64 6c 3b 20 65 6c 73 65 20 7b 20 63 65 endl; else { ce
05f0: 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c rr << "FAILED" <
0600: 3c 20 65 6e 64 6c 3b 20 63 65 72 72 20 3c 3c 20 < endl; cerr <<
0610: 22 5c 74 45 78 70 65 63 74 65 64 3a 20 22 20 3c "\tExpected: " <
0620: 3c 20 70 72 69 6e 74 5f 61 72 72 61 79 28 45 78 < print_array(Ex
0630: 70 65 63 74 65 64 29 20 3c 3c 20 65 6e 64 6c 3b pected) << endl;
0640: 20 63 65 72 72 20 3c 3c 20 22 5c 74 52 65 63 65 cerr << "\tRece
0650: 69 76 65 64 3a 20 22 20 3c 3c 20 70 72 69 6e 74 ived: " << print
0660: 5f 61 72 72 61 79 28 52 65 63 65 69 76 65 64 29 _array(Received)
0670: 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 72 65 74 75 << endl; } retu
0680: 72 6e 20 30 3b 7d 0d 0a 0d 0a 74 65 6d 70 6c 61 rn 0;}....templa
0690: 74 65 3c 69 6e 74 20 4e 3e 20 73 74 72 75 63 74 te<int N> struct
06a0: 20 43 61 73 65 5f 20 7b 7d 3b 0d 0a 63 68 61 72 Case_ {};..char
06b0: 20 54 65 73 74 5f 28 2e 2e 2e 29 3b 0d 0a 69 6e Test_(...);..in
06c0: 74 20 54 65 73 74 5f 28 43 61 73 65 5f 3c 30 3e t Test_(Case_<0>
06d0: 29 20 7b 0d 0a 09 73 74 72 69 6e 67 20 6e 20 3d ) {...string n =
06e0: 20 22 32 37 22 3b 20 0d 0a 09 69 6e 74 20 52 65 "27"; ...int Re
06f0: 74 56 61 6c 5f 5b 5d 20 3d 20 7b 33 2c 20 33 20 tVal_[] = {3, 3
0700: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0710: 6e 74 3e 20 52 65 74 56 61 6c 28 52 65 74 56 61 nt> RetVal(RetVa
0720: 6c 5f 2c 20 52 65 74 56 61 6c 5f 2b 73 69 7a 65 l_, RetVal_+size
0730: 6f 66 28 52 65 74 56 61 6c 5f 29 2f 73 69 7a 65 of(RetVal_)/size
0740: 6f 66 28 2a 52 65 74 56 61 6c 5f 29 29 3b 20 0d of(*RetVal_)); .
0750: 0a 09 72 65 74 75 72 6e 20 76 65 72 69 66 79 5f ..return verify_
0760: 63 61 73 65 28 52 65 74 56 61 6c 2c 20 53 74 72 case(RetVal, Str
0770: 6f 6e 67 50 72 69 6d 65 50 6f 77 65 72 28 29 2e ongPrimePower().
0780: 62 61 73 65 41 6e 64 45 78 70 6f 6e 65 6e 74 28 baseAndExponent(
0790: 6e 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 74 n)); }..int Test
07a0: 5f 28 43 61 73 65 5f 3c 31 3e 29 20 7b 0d 0a 09 _(Case_<1>) {...
07b0: 73 74 72 69 6e 67 20 6e 20 3d 20 22 31 30 22 3b string n = "10";
07c0: 20 0d 0a 09 76 65 63 74 6f 72 20 3c 69 6e 74 3e ...vector <int>
07d0: 20 52 65 74 56 61 6c 3b 20 0d 0a 09 72 65 74 75 RetVal; ...retu
07e0: 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 28 52 rn verify_case(R
07f0: 65 74 56 61 6c 2c 20 53 74 72 6f 6e 67 50 72 69 etVal, StrongPri
0800: 6d 65 50 6f 77 65 72 28 29 2e 62 61 73 65 41 6e mePower().baseAn
0810: 64 45 78 70 6f 6e 65 6e 74 28 6e 29 29 3b 20 7d dExponent(n)); }
0820: 0d 0a 69 6e 74 20 54 65 73 74 5f 28 43 61 73 65 ..int Test_(Case
0830: 5f 3c 32 3e 29 20 7b 0d 0a 09 73 74 72 69 6e 67 _<2>) {...string
0840: 20 6e 20 3d 20 22 37 22 3b 20 0d 0a 09 76 65 63 n = "7"; ...vec
0850: 74 6f 72 20 3c 69 6e 74 3e 20 52 65 74 56 61 6c tor <int> RetVal
0860: 3b 20 0d 0a 09 72 65 74 75 72 6e 20 76 65 72 69 ; ...return veri
0870: 66 79 5f 63 61 73 65 28 52 65 74 56 61 6c 2c 20 fy_case(RetVal,
0880: 53 74 72 6f 6e 67 50 72 69 6d 65 50 6f 77 65 72 StrongPrimePower
0890: 28 29 2e 62 61 73 65 41 6e 64 45 78 70 6f 6e 65 ().baseAndExpone
08a0: 6e 74 28 6e 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 nt(n)); }..int T
08b0: 65 73 74 5f 28 43 61 73 65 5f 3c 33 3e 29 20 7b est_(Case_<3>) {
08c0: 0d 0a 09 73 74 72 69 6e 67 20 6e 20 3d 20 22 31 ...string n = "1
08d0: 32 39 36 22 3b 20 0d 0a 09 76 65 63 74 6f 72 20 296"; ...vector
08e0: 3c 69 6e 74 3e 20 52 65 74 56 61 6c 3b 20 0d 0a <int> RetVal; ..
08f0: 09 72 65 74 75 72 6e 20 76 65 72 69 66 79 5f 63 .return verify_c
0900: 61 73 65 28 52 65 74 56 61 6c 2c 20 53 74 72 6f ase(RetVal, Stro
0910: 6e 67 50 72 69 6d 65 50 6f 77 65 72 28 29 2e 62 ngPrimePower().b
0920: 61 73 65 41 6e 64 45 78 70 6f 6e 65 6e 74 28 6e aseAndExponent(n
0930: 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 74 5f )); }..int Test_
0940: 28 43 61 73 65 5f 3c 34 3e 29 20 7b 0d 0a 09 73 (Case_<4>) {...s
0950: 74 72 69 6e 67 20 6e 20 3d 20 22 35 37 36 34 36 tring n = "57646
0960: 30 37 35 32 33 30 33 34 32 33 34 38 38 22 3b 20 0752303423488";
0970: 0d 0a 09 69 6e 74 20 52 65 74 56 61 6c 5f 5b 5d ...int RetVal_[]
0980: 20 3d 20 7b 32 2c 20 35 39 20 7d 3b 0d 0a 09 20 = {2, 59 };...
0990: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 52 65 vector <int> Re
09a0: 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c 20 52 65 tVal(RetVal_, Re
09b0: 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 52 65 74 tVal_+sizeof(Ret
09c0: 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a 52 65 Val_)/sizeof(*Re
09d0: 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 65 74 75 tVal_)); ...retu
09e0: 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 28 52 rn verify_case(R
09f0: 65 74 56 61 6c 2c 20 53 74 72 6f 6e 67 50 72 69 etVal, StrongPri
0a00: 6d 65 50 6f 77 65 72 28 29 2e 62 61 73 65 41 6e mePower().baseAn
0a10: 64 45 78 70 6f 6e 65 6e 74 28 6e 29 29 3b 20 7d dExponent(n)); }
0a20: 0d 0a 69 6e 74 20 54 65 73 74 5f 28 43 61 73 65 ..int Test_(Case
0a30: 5f 3c 35 3e 29 20 7b 0d 0a 09 73 74 72 69 6e 67 _<5>) {...string
0a40: 20 6e 20 3d 20 22 39 39 39 39 39 39 38 37 34 30 n = "9999998740
0a50: 30 30 30 30 33 39 36 39 22 3b 20 0d 0a 09 69 6e 00003969"; ...in
0a60: 74 20 52 65 74 56 61 6c 5f 5b 5d 20 3d 20 7b 39 t RetVal_[] = {9
0a70: 39 39 39 39 39 39 33 37 2c 20 32 20 7d 3b 0d 0a 99999937, 2 };..
0a80: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0a90: 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c 20 RetVal(RetVal_,
0aa0: 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 52 RetVal_+sizeof(R
0ab0: 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a etVal_)/sizeof(*
0ac0: 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 65 RetVal_)); ...re
0ad0: 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 turn verify_case
0ae0: 28 52 65 74 56 61 6c 2c 20 53 74 72 6f 6e 67 50 (RetVal, StrongP
0af0: 72 69 6d 65 50 6f 77 65 72 28 29 2e 62 61 73 65 rimePower().base
0b00: 41 6e 64 45 78 70 6f 6e 65 6e 74 28 6e 29 29 3b AndExponent(n));
0b10: 20 7d 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 3c 69 }....template<i
0b20: 6e 74 20 4e 3e 20 76 6f 69 64 20 52 75 6e 5f 28 nt N> void Run_(
0b30: 29 20 7b 20 63 65 72 72 20 3c 3c 20 22 54 65 73 ) { cerr << "Tes
0b40: 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c t Case #" << N <
0b50: 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 < "..." << flush
0b60: 3b 20 54 65 73 74 5f 28 43 61 73 65 5f 3c 4e 3e ; Test_(Case_<N>
0b70: 28 29 29 3b 20 52 75 6e 5f 3c 73 69 7a 65 6f 66 ()); Run_<sizeof
0b80: 28 54 65 73 74 5f 28 43 61 73 65 5f 3c 4e 2b 31 (Test_(Case_<N+1
0b90: 3e 28 29 29 29 3d 3d 31 20 3f 20 2d 31 20 3a 20 >()))==1 ? -1 :
0ba0: 4e 2b 31 3e 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c N+1>(); }..templ
0bb0: 61 74 65 3c 3e 20 20 20 20 20 20 76 6f 69 64 20 ate<> void
0bc0: 52 75 6e 5f 3c 2d 31 3e 28 29 20 7b 7d 0d 0a 69 Run_<-1>() {}..i
0bd0: 6e 74 20 6d 61 69 6e 28 29 20 7b 20 52 75 6e 5f nt main() { Run_
0be0: 3c 30 3e 28 29 3b 20 7d 0d 0a 2f 2f 20 45 4e 44 <0>(); }..// END
0bf0: 20 43 55 54 20 48 45 52 45 0d 0a 0d 0a CUT HERE....