Artifact efa6784811dbad8ed94306ad1158941de8fa63eb:
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 75 73 69 6e de <cmath>..usin
0110: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0120: 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c ..typedef long l
0130: 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 63 6c 61 73 73 ong LL;....class
0140: 20 52 65 66 61 63 74 6f 72 61 62 6c 65 4e 75 6d RefactorableNum
0150: 62 65 72 0d 0a 7b 0d 0a 70 75 62 6c 69 63 3a 0d ber..{..public:.
0160: 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 50 3b ..vector<int> P;
0170: 0d 0a 0d 0a 09 69 6e 74 20 63 6f 75 6e 74 28 69 .....int count(i
0180: 6e 74 20 6c 6f 77 2c 20 69 6e 74 20 68 69 67 68 nt low, int high
0190: 29 20 0d 0a 09 7b 0d 0a 09 09 50 2e 63 6c 65 61 ) ...{....P.clea
01a0: 72 28 29 3b 0d 0a 09 09 76 65 63 74 6f 72 3c 62 r();....vector<b
01b0: 6f 6f 6c 3e 20 69 73 50 28 32 30 30 30 2c 20 74 ool> isP(2000, t
01c0: 72 75 65 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 rue);....for(int
01d0: 20 70 3d 32 3b 20 70 3c 32 30 30 30 3b 20 2b 2b p=2; p<2000; ++
01e0: 70 29 0d 0a 09 09 09 69 66 28 20 69 73 50 5b 70 p).....if( isP[p
01f0: 5d 20 29 20 7b 0d 0a 09 09 09 09 50 2e 70 75 73 ] ) {......P.pus
0200: 68 5f 62 61 63 6b 28 70 29 3b 0d 0a 09 09 09 09 h_back(p);......
0210: 66 6f 72 28 69 6e 74 20 71 3d 70 2a 70 3b 20 71 for(int q=p*p; q
0220: 3c 32 30 30 30 3b 20 71 2b 3d 70 29 0d 0a 09 09 <2000; q+=p)....
0230: 09 09 09 69 73 50 5b 71 5d 20 3d 20 66 61 6c 73 ...isP[q] = fals
0240: 65 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 09 69 6e e;.....}......in
0250: 74 20 63 6e 74 20 3d 20 30 3b 0d 0a 09 09 66 6f t cnt = 0;....fo
0260: 72 28 69 6e 74 20 6e 3d 6c 6f 77 3b 20 6e 3c 3d r(int n=low; n<=
0270: 68 69 67 68 3b 20 2b 2b 6e 29 0d 0a 09 09 09 69 high; ++n).....i
0280: 66 28 20 72 65 66 28 6e 29 20 29 0d 0a 09 09 09 f( ref(n) ).....
0290: 09 2b 2b 63 6e 74 3b 0d 0a 09 09 72 65 74 75 72 .++cnt;....retur
02a0: 6e 20 63 6e 74 3b 0d 0a 09 7d 0d 0a 0d 0a 09 62 n cnt;...}.....b
02b0: 6f 6f 6c 20 72 65 66 28 69 6e 74 20 4e 29 0d 0a ool ref(int N)..
02c0: 09 7b 0d 0a 09 09 69 6e 74 20 6e 20 3d 20 4e 3b .{....int n = N;
02d0: 0d 0a 09 09 69 6e 74 20 78 20 3d 20 31 3b 0d 0a ....int x = 1;..
02e0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
02f0: 3c 50 2e 73 69 7a 65 28 29 20 26 26 20 6e 3e 31 <P.size() && n>1
0300: 3b 20 2b 2b 69 29 0d 0a 09 09 7b 0d 0a 09 09 09 ; ++i)....{.....
0310: 69 6e 74 20 70 20 3d 20 50 5b 69 5d 3b 0d 0a 09 int p = P[i];...
0320: 09 09 69 66 28 20 70 2a 70 20 3e 20 6e 20 29 0d ..if( p*p > n ).
0330: 0a 09 09 09 09 62 72 65 61 6b 3b 0d 0a 09 09 09 .....break;.....
0340: 69 6e 74 20 63 20 3d 20 30 3b 0d 0a 09 09 09 77 int c = 0;.....w
0350: 68 69 6c 65 28 6e 25 70 3d 3d 30 29 0d 0a 09 09 hile(n%p==0)....
0360: 09 09 6e 2f 3d 70 2c 20 2b 2b 63 3b 0d 0a 09 09 ..n/=p, ++c;....
0370: 09 78 20 2a 3d 20 63 2b 31 3b 0d 0a 09 09 7d 0d .x *= c+1;....}.
0380: 0a 09 09 69 66 28 6e 3e 31 29 0d 0a 09 09 09 78 ...if(n>1).....x
0390: 20 2a 3d 20 32 3b 0d 0a 09 09 72 65 74 75 72 6e *= 2;....return
03a0: 20 4e 25 78 20 3d 3d 20 30 3b 0d 0a 09 7d 0d 0a N%x == 0;...}..
03b0: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
03c0: 45 52 45 0d 0a 09 70 75 62 6c 69 63 3a 0d 0a 09 ERE...public:...
03d0: 76 6f 69 64 20 72 75 6e 5f 74 65 73 74 28 69 6e void run_test(in
03e0: 74 20 43 61 73 65 29 20 7b 20 69 66 20 28 28 43 t Case) { if ((C
03f0: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0400: 61 73 65 20 3d 3d 20 30 29 29 20 74 65 73 74 5f ase == 0)) test_
0410: 63 61 73 65 5f 30 28 29 3b 20 69 66 20 28 28 43 case_0(); if ((C
0420: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0430: 61 73 65 20 3d 3d 20 31 29 29 20 74 65 73 74 5f ase == 1)) test_
0440: 63 61 73 65 5f 31 28 29 3b 20 69 66 20 28 28 43 case_1(); if ((C
0450: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0460: 61 73 65 20 3d 3d 20 32 29 29 20 74 65 73 74 5f ase == 2)) test_
0470: 63 61 73 65 5f 32 28 29 3b 20 69 66 20 28 28 43 case_2(); if ((C
0480: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0490: 61 73 65 20 3d 3d 20 33 29 29 20 74 65 73 74 5f ase == 3)) test_
04a0: 63 61 73 65 5f 33 28 29 3b 20 7d 0d 0a 09 70 72 case_3(); }...pr
04b0: 69 76 61 74 65 3a 0d 0a 09 74 65 6d 70 6c 61 74 ivate:...templat
04c0: 65 20 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 73 e <typename T> s
04d0: 74 72 69 6e 67 20 70 72 69 6e 74 5f 61 72 72 61 tring print_arra
04e0: 79 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 y(const vector<T
04f0: 3e 20 26 56 29 20 7b 20 6f 73 74 72 69 6e 67 73 > &V) { ostrings
0500: 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 tream os; os <<
0510: 22 7b 20 22 3b 20 66 6f 72 20 28 74 79 70 65 6e "{ "; for (typen
0520: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
0530: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
0540: 65 72 20 3d 20 56 2e 62 65 67 69 6e 28 29 3b 20 er = V.begin();
0550: 69 74 65 72 20 21 3d 20 56 2e 65 6e 64 28 29 3b iter != V.end();
0560: 20 2b 2b 69 74 65 72 29 20 6f 73 20 3c 3c 20 27 ++iter) os << '
0570: 5c 22 27 20 3c 3c 20 2a 69 74 65 72 20 3c 3c 20 \"' << *iter <<
0580: 22 5c 22 2c 22 3b 20 6f 73 20 3c 3c 20 22 20 7d "\","; os << " }
0590: 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 "; return os.str
05a0: 28 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 76 65 72 (); }...void ver
05b0: 69 66 79 5f 63 61 73 65 28 69 6e 74 20 43 61 73 ify_case(int Cas
05c0: 65 2c 20 63 6f 6e 73 74 20 69 6e 74 20 26 45 78 e, const int &Ex
05d0: 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 69 6e pected, const in
05e0: 74 20 26 52 65 63 65 69 76 65 64 29 20 7b 20 63 t &Received) { c
05f0: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
0600: 65 20 23 22 20 3c 3c 20 43 61 73 65 20 3c 3c 20 e #" << Case <<
0610: 22 2e 2e 2e 22 3b 20 69 66 20 28 45 78 70 65 63 "..."; if (Expec
0620: 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 ted == Received)
0630: 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 cerr << "PASSED
0640: 22 20 3c 3c 20 65 6e 64 6c 3b 20 65 6c 73 65 20 " << endl; else
0650: 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 { cerr << "FAILE
0660: 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 63 65 72 72 D" << endl; cerr
0670: 20 3c 3c 20 22 5c 74 45 78 70 65 63 74 65 64 3a << "\tExpected:
0680: 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 \"" << Expected
0690: 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c << '\"' << endl
06a0: 3b 20 63 65 72 72 20 3c 3c 20 22 5c 74 52 65 63 ; cerr << "\tRec
06b0: 65 69 76 65 64 3a 20 5c 22 22 20 3c 3c 20 52 65 eived: \"" << Re
06c0: 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c ceived << '\"' <
06d0: 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 09 76 6f < endl; } }...vo
06e0: 69 64 20 74 65 73 74 5f 63 61 73 65 5f 30 28 29 id test_case_0()
06f0: 20 7b 20 69 6e 74 20 41 72 67 30 20 3d 20 31 3b { int Arg0 = 1;
0700: 20 69 6e 74 20 41 72 67 31 20 3d 20 31 30 3b 20 int Arg1 = 10;
0710: 69 6e 74 20 41 72 67 32 20 3d 20 34 3b 20 76 65 int Arg2 = 4; ve
0720: 72 69 66 79 5f 63 61 73 65 28 30 2c 20 41 72 67 rify_case(0, Arg
0730: 32 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c 20 41 2, count(Arg0, A
0740: 72 67 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 rg1)); }...void
0750: 74 65 73 74 5f 63 61 73 65 5f 31 28 29 20 7b 20 test_case_1() {
0760: 69 6e 74 20 41 72 67 30 20 3d 20 31 30 3b 20 69 int Arg0 = 10; i
0770: 6e 74 20 41 72 67 31 20 3d 20 31 30 30 3b 20 69 nt Arg1 = 100; i
0780: 6e 74 20 41 72 67 32 20 3d 20 31 32 3b 20 76 65 nt Arg2 = 12; ve
0790: 72 69 66 79 5f 63 61 73 65 28 31 2c 20 41 72 67 rify_case(1, Arg
07a0: 32 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c 20 41 2, count(Arg0, A
07b0: 72 67 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 rg1)); }...void
07c0: 74 65 73 74 5f 63 61 73 65 5f 32 28 29 20 7b 20 test_case_2() {
07d0: 69 6e 74 20 41 72 67 30 20 3d 20 32 35 3b 20 69 int Arg0 = 25; i
07e0: 6e 74 20 41 72 67 31 20 3d 20 33 35 3b 20 69 6e nt Arg1 = 35; in
07f0: 74 20 41 72 67 32 20 3d 20 30 3b 20 76 65 72 69 t Arg2 = 0; veri
0800: 66 79 5f 63 61 73 65 28 32 2c 20 41 72 67 32 2c fy_case(2, Arg2,
0810: 20 63 6f 75 6e 74 28 41 72 67 30 2c 20 41 72 67 count(Arg0, Arg
0820: 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 1)); }...void te
0830: 73 74 5f 63 61 73 65 5f 33 28 29 20 7b 20 69 6e st_case_3() { in
0840: 74 20 41 72 67 30 20 3d 20 31 32 33 3b 20 69 6e t Arg0 = 123; in
0850: 74 20 41 72 67 31 20 3d 20 34 35 36 37 3b 20 69 t Arg1 = 4567; i
0860: 6e 74 20 41 72 67 32 20 3d 20 33 31 35 3b 20 76 nt Arg2 = 315; v
0870: 65 72 69 66 79 5f 63 61 73 65 28 33 2c 20 41 72 erify_case(3, Ar
0880: 67 32 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c 20 g2, count(Arg0,
0890: 41 72 67 31 29 29 3b 20 7d 0d 0a 0d 0a 2f 2f 20 Arg1)); }....//
08a0: 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a 7d 3b END CUT HERE..};
08b0: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
08c0: 45 52 45 20 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 ERE ..int main()
08d0: 20 7b 0d 0a 09 52 65 66 61 63 74 6f 72 61 62 6c {...Refactorabl
08e0: 65 4e 75 6d 62 65 72 28 29 2e 72 75 6e 5f 74 65 eNumber().run_te
08f0: 73 74 28 2d 31 29 3b 0d 0a 7d 0d 0a 2f 2f 20 45 st(-1);..}..// E
0900: 4e 44 20 43 55 54 20 48 45 52 45 0d 0a ND CUT HERE..