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 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 23 69 66 64 65 <cstring>..#ifde
0150: 66 20 5f 5f 47 4e 55 43 5f 5f 0d 0a 23 69 6e 63 f __GNUC__..#inc
0160: 6c 75 64 65 20 3c 65 78 74 2f 68 61 73 68 5f 6d lude <ext/hash_m
0170: 61 70 3e 0d 0a 23 64 65 66 69 6e 65 20 75 6e 6f ap>..#define uno
0180: 72 64 65 72 65 64 5f 6d 61 70 20 5f 5f 67 6e 75 rdered_map __gnu
0190: 5f 63 78 78 3a 3a 68 61 73 68 5f 6d 61 70 0d 0a _cxx::hash_map..
01a0: 23 65 6c 73 65 0d 0a 23 69 6e 63 6c 75 64 65 20 #else..#include
01b0: 3c 75 6e 6f 72 64 65 72 65 64 5f 6d 61 70 3e 0d <unordered_map>.
01c0: 0a 23 65 6e 64 69 66 0d 0a 75 73 69 6e 67 20 6e .#endif..using n
01d0: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
01e0: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
01f0: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0200: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0210: 50 3b 0d 0a 0d 0a 4c 4c 20 67 63 64 28 4c 4c 20 P;....LL gcd(LL
0220: 61 2c 20 4c 4c 20 62 29 0d 0a 7b 0d 0a 09 77 68 a, LL b)..{...wh
0230: 69 6c 65 28 61 29 0d 0a 09 09 73 77 61 70 28 61 ile(a)....swap(a
0240: 2c 20 62 25 3d 61 29 3b 0d 0a 09 72 65 74 75 72 , b%=a);...retur
0250: 6e 20 62 3b 0d 0a 7d 0d 0a 0a 63 6c 61 73 73 20 n b;..}...class
0260: 45 6c 6c 79 73 4e 75 6d 62 65 72 73 20 7b 20 70 EllysNumbers { p
0270: 75 62 6c 69 63 3a 0d 0a 09 6c 6f 6e 67 20 6c 6f ublic:...long lo
0280: 6e 67 20 67 65 74 53 75 62 73 65 74 73 28 6c 6f ng getSubsets(lo
0290: 6e 67 20 6c 6f 6e 67 20 6e 2c 20 76 65 63 74 6f ng long n, vecto
02a0: 72 20 3c 73 74 72 69 6e 67 3e 20 73 70 65 63 69 r <string> speci
02b0: 61 6c 29 0d 0a 09 7b 0d 0a 09 09 76 65 63 74 6f al)...{....vecto
02c0: 72 3c 4c 4c 3e 20 73 70 3b 20 7b 0d 0a 09 09 09 r<LL> sp; {.....
02d0: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 73 69 6e stringstream sin
02e0: 28 20 61 63 63 75 6d 75 6c 61 74 65 28 73 70 65 ( accumulate(spe
02f0: 63 69 61 6c 2e 62 65 67 69 6e 28 29 2c 20 73 70 cial.begin(), sp
0300: 65 63 69 61 6c 2e 65 6e 64 28 29 2c 20 73 74 72 ecial.end(), str
0310: 69 6e 67 28 22 22 29 29 20 29 3b 0d 0a 09 09 09 ing("")) );.....
0320: 66 6f 72 28 4c 4c 20 76 3b 20 73 69 6e 3e 3e 76 for(LL v; sin>>v
0330: 3b 20 29 0d 0a 09 09 09 09 69 66 28 6e 25 76 3d ; )......if(n%v=
0340: 3d 30 20 26 26 20 67 63 64 28 6e 2f 76 2c 76 29 =0 && gcd(n/v,v)
0350: 3d 3d 31 29 0d 0a 09 09 09 09 09 73 70 2e 70 75 ==1).......sp.pu
0360: 73 68 5f 62 61 63 6b 28 76 29 3b 0d 0a 09 09 7d sh_back(v);....}
0370: 0d 0a 0d 0a 09 09 6d 61 70 3c 4c 4c 2c 20 4c 4c ......map<LL, LL
0380: 3e 20 77 3b 0d 0a 09 09 77 5b 6e 5d 20 3d 20 31 > w;....w[n] = 1
0390: 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 ;....for(int i=0
03a0: 3b 20 69 3c 73 70 2e 73 69 7a 65 28 29 3b 20 2b ; i<sp.size(); +
03b0: 2b 69 29 0d 0a 09 09 09 66 6f 72 28 6d 61 70 3c +i).....for(map<
03c0: 4c 4c 2c 20 4c 4c 3e 3a 3a 69 74 65 72 61 74 6f LL, LL>::iterato
03d0: 72 20 69 74 3d 77 2e 62 65 67 69 6e 28 29 3b 20 r it=w.begin();
03e0: 69 74 21 3d 77 2e 65 6e 64 28 29 3b 20 2b 2b 69 it!=w.end(); ++i
03f0: 74 29 0d 0a 09 09 09 09 69 66 28 69 74 2d 3e 66 t)......if(it->f
0400: 69 72 73 74 25 73 70 5b 69 5d 3d 3d 30 29 0d 0a irst%sp[i]==0)..
0410: 09 09 09 09 09 77 5b 69 74 2d 3e 66 69 72 73 74 .....w[it->first
0420: 2f 73 70 5b 69 5d 5d 20 2b 3d 20 69 74 2d 3e 73 /sp[i]] += it->s
0430: 65 63 6f 6e 64 3b 0d 0a 09 09 72 65 74 75 72 6e econd;....return
0440: 20 77 5b 31 5d 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a w[1];...}..};..
0450: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0460: 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 ERE..#include <c
0470: 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 time>..double st
0480: 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 art_time; string
0490: 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 timer().. { ost
04a0: 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f ringstream os; o
04b0: 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 s << " (" << int
04c0: 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f ((clock()-start_
04d0: 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 time)/CLOCKS_PER
04e0: 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 _SEC*1000) << "
04f0: 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f msec)"; return o
0500: 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 s.str(); }..temp
0510: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e late<typename T>
0520: 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 ostream& operat
0530: 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 or<<(ostream& os
0540: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
0550: 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 >& v).. { os <<
0560: 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 "{ ";.. for(ty
0570: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e pename vector<T>
0580: 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 ::const_iterator
0590: 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 it=v.begin(); i
05a0: 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 t!=v.end(); ++it
05b0: 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 ).. os << '\"'
05c0: 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 << *it << '\"'
05d0: 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 << (it+1==v.end(
05e0: 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 ) ? "" : ", ");
05f0: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
0600: 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 rn os; }..void v
0610: 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 erify_case(const
0620: 20 6c 6f 6e 67 20 6c 6f 6e 67 26 20 45 78 70 65 long long& Expe
0630: 63 74 65 64 2c 20 63 6f 6e 73 74 20 6c 6f 6e 67 cted, const long
0640: 20 6c 6f 6e 67 26 20 52 65 63 65 69 76 65 64 29 long& Received)
0650: 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 {.. bool ok = (
0660: 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 Expected == Rece
0670: 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 ived);.. if(ok)
0680: 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 cerr << "PASSED"
0690: 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 << timer() << e
06a0: 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 ndl; else { cer
06b0: 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c r << "FAILED" <<
06c0: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
06d0: 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f ;.. cerr << "\to
06e0: 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 : \"" << Expecte
06f0: 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 d << '\"' << end
0700: 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c l << "\tx: \"" <
0710: 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c < Received << '\
0720: 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d "' << endl; } }.
0730: 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 4e 29 .#define CASE(N)
0740: 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 {cerr << "Test
0750: 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 Case #" << N <<
0760: 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 "..." << flush;
0770: 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b start_time=clock
0780: 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 ();..#define END
0790: 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 5f 2c . verify_case(_,
07a0: 20 45 6c 6c 79 73 4e 75 6d 62 65 72 73 28 29 2e EllysNumbers().
07b0: 67 65 74 53 75 62 73 65 74 73 28 6e 2c 20 73 70 getSubsets(n, sp
07c0: 65 63 69 61 6c 29 29 3b 7d 0d 0a 69 6e 74 20 6d ecial));}..int m
07d0: 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 ain(){....CASE(0
07e0: 29 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 6e 20 )...long long n
07f0: 3d 20 31 32 4c 4c 3b 20 0d 0a 09 73 74 72 69 6e = 12LL; ...strin
0800: 67 20 73 70 65 63 69 61 6c 5f 5b 5d 20 3d 20 7b g special_[] = {
0810: 22 34 20 32 20 35 20 36 20 33 22 7d 3b 0d 0a 09 "4 2 5 6 3"};...
0820: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
0830: 3e 20 73 70 65 63 69 61 6c 28 73 70 65 63 69 61 > special(specia
0840: 6c 5f 2c 20 73 70 65 63 69 61 6c 5f 2b 73 69 7a l_, special_+siz
0850: 65 6f 66 28 73 70 65 63 69 61 6c 5f 29 2f 73 69 eof(special_)/si
0860: 7a 65 6f 66 28 2a 73 70 65 63 69 61 6c 5f 29 29 zeof(*special_))
0870: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f ; ...long long _
0880: 20 3d 20 31 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 = 1LL; ..END..C
0890: 41 53 45 28 31 29 0d 0a 09 6c 6f 6e 67 20 6c 6f ASE(1)...long lo
08a0: 6e 67 20 6e 20 3d 20 34 32 4c 4c 3b 20 0d 0a 09 ng n = 42LL; ...
08b0: 73 74 72 69 6e 67 20 73 70 65 63 69 61 6c 5f 5b string special_[
08c0: 5d 20 3d 20 7b 22 31 20 32 20 33 20 34 20 35 20 ] = {"1 2 3 4 5
08d0: 36 20 37 20 31 33 20 31 34 20 32 31 20 34 32 22 6 7 13 14 21 42"
08e0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
08f0: 74 72 69 6e 67 3e 20 73 70 65 63 69 61 6c 28 73 tring> special(s
0900: 70 65 63 69 61 6c 5f 2c 20 73 70 65 63 69 61 6c pecial_, special
0910: 5f 2b 73 69 7a 65 6f 66 28 73 70 65 63 69 61 6c _+sizeof(special
0920: 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 70 65 63 69 _)/sizeof(*speci
0930: 61 6c 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c al_)); ...long l
0940: 6f 6e 67 20 5f 20 3d 20 31 30 4c 4c 3b 20 0d 0a ong _ = 10LL; ..
0950: 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 6c END..CASE(2)...l
0960: 6f 6e 67 20 6c 6f 6e 67 20 6e 20 3d 20 31 33 33 ong long n = 133
0970: 37 4c 4c 3b 20 0d 0a 09 73 74 72 69 6e 67 20 73 7LL; ...string s
0980: 70 65 63 69 61 6c 5f 5b 5d 20 3d 20 7b 22 31 20 pecial_[] = {"1
0990: 31 33 20 34 32 20 36 36 36 20 32 36 37 34 22 7d 13 42 666 2674"}
09a0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
09b0: 72 69 6e 67 3e 20 73 70 65 63 69 61 6c 28 73 70 ring> special(sp
09c0: 65 63 69 61 6c 5f 2c 20 73 70 65 63 69 61 6c 5f ecial_, special_
09d0: 2b 73 69 7a 65 6f 66 28 73 70 65 63 69 61 6c 5f +sizeof(special_
09e0: 29 2f 73 69 7a 65 6f 66 28 2a 73 70 65 63 69 61 )/sizeof(*specia
09f0: 6c 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f l_)); ...long lo
0a00: 6e 67 20 5f 20 3d 20 30 4c 4c 3b 20 0d 0a 45 4e ng _ = 0LL; ..EN
0a10: 44 0d 0a 43 41 53 45 28 33 29 0d 0a 09 6c 6f 6e D..CASE(3)...lon
0a20: 67 20 6c 6f 6e 67 20 6e 20 3d 20 31 30 37 33 37 g long n = 10737
0a30: 34 31 38 32 34 4c 4c 3b 20 0d 0a 09 73 74 72 69 41824LL; ...stri
0a40: 6e 67 20 73 70 65 63 69 61 6c 5f 5b 5d 20 3d 20 ng special_[] =
0a50: 7b 22 31 20 32 20 34 20 38 20 31 36 20 33 32 20 {"1 2 4 8 16 32
0a60: 36 34 20 31 32 38 20 32 35 36 20 35 31 32 20 31 64 128 256 512 1
0a70: 30 32 34 20 32 30 34 38 20 34 30 39 36 20 38 31 024 2048 4096 81
0a80: 39 32 20 31 22 2c 0d 0a 20 22 36 33 38 34 20 33 92 1",.. "6384 3
0a90: 32 37 36 38 20 36 35 35 33 36 20 31 33 31 30 37 2768 65536 13107
0aa0: 32 20 32 36 32 31 34 34 20 35 32 34 32 38 38 20 2 262144 524288
0ab0: 31 30 34 38 35 37 36 20 32 30 39 37 22 2c 0d 0a 1048576 2097",..
0ac0: 20 22 31 35 32 20 34 31 39 34 33 30 34 20 38 33 "152 4194304 83
0ad0: 38 38 36 30 38 20 31 36 37 37 37 32 31 36 20 33 88608 16777216 3
0ae0: 33 35 35 34 34 33 32 20 36 37 31 30 38 38 36 34 3554432 67108864
0af0: 20 31 33 34 22 2c 0d 0a 20 22 32 31 37 37 32 38 134",.. "217728
0b00: 20 32 36 38 34 33 35 34 35 36 20 35 33 36 38 37 268435456 53687
0b10: 30 39 31 32 22 7d 3b 0d 0a 09 20 20 76 65 63 74 0912"};... vect
0b20: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 70 65 63 or <string> spec
0b30: 69 61 6c 28 73 70 65 63 69 61 6c 5f 2c 20 73 70 ial(special_, sp
0b40: 65 63 69 61 6c 5f 2b 73 69 7a 65 6f 66 28 73 70 ecial_+sizeof(sp
0b50: 65 63 69 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a ecial_)/sizeof(*
0b60: 73 70 65 63 69 61 6c 5f 29 29 3b 20 0d 0a 09 6c special_)); ...l
0b70: 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 30 4c 4c ong long _ = 0LL
0b80: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 ; ..END..CASE(4)
0b90: 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 6e 20 3d ...long long n =
0ba0: 20 37 34 32 30 37 33 38 31 33 34 38 31 30 4c 4c 7420738134810LL
0bb0: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 73 70 65 63 ; ...string spec
0bc0: 69 61 6c 5f 5b 5d 20 3d 20 7b 22 34 33 35 20 36 ial_[] = {"435 6
0bd0: 32 35 31 39 39 30 35 35 20 34 31 39 39 20 33 33 25199055 4199 33
0be0: 32 36 33 20 31 37 20 32 32 32 38 37 30 20 32 38 263 17 222870 28
0bf0: 34 38 37 30 34 33 33 20 37 32 30 39 33 22 2c 0d 4870433 72093",.
0c00: 0a 20 22 32 33 37 39 20 37 20 31 31 20 33 31 20 . "2379 7 11 31
0c10: 32 34 37 31 31 30 38 32 37 20 32 33 20 31 37 37 247110827 23 177
0c20: 31 20 38 31 38 30 39 20 38 35 31 39 36 38 34 38 1 81809 85196848
0c30: 37 20 31 33 20 22 2c 20 0d 0a 20 22 34 37 36 33 7 13 ", .. "4763
0c40: 37 39 37 39 35 20 31 30 30 31 20 35 20 34 33 35 79795 1001 5 435
0c50: 32 37 34 31 31 34 20 33 38 32 36 34 35 35 34 20 274114 38264554
0c60: 37 34 32 39 20 32 33 39 39 30 36 35 32 35 22 2c 7429 239906525",
0c70: 0d 0a 20 22 20 33 20 32 32 37 31 38 33 37 30 36 .. " 3 227183706
0c80: 20 38 38 37 30 34 35 34 31 34 20 36 30 36 37 38 887045414 60678
0c90: 36 36 37 30 20 33 37 39 35 20 37 39 37 36 30 35 6670 3795 797605
0ca0: 31 37 35 20 32 39 22 2c 0d 0a 20 22 20 33 30 20 175 29",.. " 30
0cb0: 37 34 37 31 38 36 37 31 39 20 31 39 20 32 20 35 747186719 19 2 5
0cc0: 36 32 33 34 37 38 34 33 20 37 34 20 32 32 39 34 62347843 74 2294
0cd0: 20 35 38 38 30 30 32 36 38 38 20 37 34 33 22 2c 588002688 743",
0ce0: 0d 0a 20 22 36 34 32 39 20 37 30 33 20 35 39 31 .. "6429 703 591
0cf0: 37 34 30 35 34 37 20 33 36 36 35 37 34 39 32 20 740547 36657492
0d00: 33 37 20 34 34 34 31 37 38 32 30 35 20 31 30 30 37 444178205 100
0d10: 32 30 30 31 20 32 22 2c 0d 0a 20 22 31 37 36 32 2001 2",.. "1762
0d20: 36 34 30 34 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6404"};... vect
0d30: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 70 65 63 or <string> spec
0d40: 69 61 6c 28 73 70 65 63 69 61 6c 5f 2c 20 73 70 ial(special_, sp
0d50: 65 63 69 61 6c 5f 2b 73 69 7a 65 6f 66 28 73 70 ecial_+sizeof(sp
0d60: 65 63 69 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a ecial_)/sizeof(*
0d70: 73 70 65 63 69 61 6c 5f 29 29 3b 20 0d 0a 09 6c special_)); ...l
0d80: 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 31 30 ong long _ = 110
0d90: 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 LL; ..END..CASE(
0da0: 35 29 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 6e 5)...long long n
0db0: 20 3d 20 31 4c 4c 3c 3c 34 35 3b 20 0d 0a 09 73 = 1LL<<45; ...s
0dc0: 74 72 69 6e 67 20 73 70 65 63 69 61 6c 5f 5b 5d tring special_[]
0dd0: 20 3d 20 7b 22 31 20 32 20 34 20 38 20 31 36 20 = {"1 2 4 8 16
0de0: 33 32 20 36 34 20 31 32 38 20 32 35 36 20 35 31 32 64 128 256 51
0df0: 32 20 31 30 32 34 20 32 30 34 38 20 34 30 39 36 2 1024 2048 4096
0e00: 20 38 31 39 32 20 31 36 33 38 34 22 7d 3b 0d 0a 8192 16384"};..
0e10: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
0e20: 67 3e 20 73 70 65 63 69 61 6c 28 73 70 65 63 69 g> special(speci
0e30: 61 6c 5f 2c 20 73 70 65 63 69 61 6c 5f 2b 73 69 al_, special_+si
0e40: 7a 65 6f 66 28 73 70 65 63 69 61 6c 5f 29 2f 73 zeof(special_)/s
0e50: 69 7a 65 6f 66 28 2a 73 70 65 63 69 61 6c 5f 29 izeof(*special_)
0e60: 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 ); ...long long
0e70: 5f 20 3d 20 30 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a _ = 0LL; ..END..
0e80: 43 41 53 45 28 37 29 0d 0a 09 6c 6f 6e 67 20 6c CASE(7)...long l
0e90: 6f 6e 67 20 6e 20 3d 20 36 31 34 38 38 39 37 38 ong n = 61488978
0ea0: 32 35 38 38 34 39 31 34 31 30 4c 4c 3b 0d 0a 09 2588491410LL;...
0eb0: 73 74 72 69 6e 67 20 73 70 65 63 69 61 6c 5f 5b string special_[
0ec0: 5d 20 3d 20 7b 22 32 20 33 20 35 20 37 20 31 31 ] = {"2 3 5 7 11
0ed0: 20 31 33 20 31 37 20 31 39 20 32 33 20 32 39 20 13 17 19 23 29
0ee0: 33 31 20 33 37 20 34 31 20 34 33 20 34 37 20 36 31 37 41 43 47 6
0ef0: 20 31 30 20 31 34 20 32 22 2c 20 22 32 20 32 36 10 14 2", "2 26
0f00: 20 33 34 20 33 38 20 34 36 20 35 38 20 36 32 20 34 38 46 58 62
0f10: 37 34 20 38 32 20 38 36 20 39 34 20 31 35 20 32 74 82 86 94 15 2
0f20: 31 20 33 33 20 33 39 20 35 31 20 35 37 20 22 2c 1 33 39 51 57 ",
0f30: 20 22 36 39 20 38 37 20 39 33 20 31 31 31 20 31 "69 87 93 111 1
0f40: 32 33 20 31 32 39 20 31 34 31 20 33 35 20 35 35 23 129 141 35 55
0f50: 20 36 35 20 38 35 20 39 35 20 31 31 35 20 31 34 65 85 95 115 14
0f60: 35 20 31 35 22 2c 20 22 35 20 31 38 35 20 32 30 5 15", "5 185 20
0f70: 35 20 32 31 35 20 32 33 35 20 37 37 20 39 31 20 5 215 235 77 91
0f80: 31 31 39 20 31 33 33 20 31 36 31 20 32 30 33 20 119 133 161 203
0f90: 32 31 37 20 32 35 39 20 32 38 22 2c 20 22 37 20 217 259 28", "7
0fa0: 33 30 31 20 33 32 39 20 31 34 33 20 31 38 37 20 301 329 143 187
0fb0: 32 30 39 20 32 35 33 20 33 31 39 20 33 34 31 20 209 253 319 341
0fc0: 34 30 37 20 34 35 31 20 34 37 33 20 35 31 37 20 407 451 473 517
0fd0: 22 2c 20 22 32 32 31 20 32 34 37 20 32 39 39 20 ", "221 247 299
0fe0: 33 37 37 20 34 30 33 20 34 38 31 20 35 33 33 20 377 403 481 533
0ff0: 35 35 39 20 36 31 31 20 33 32 33 20 33 39 31 20 559 611 323 391
1000: 34 39 33 20 35 32 22 2c 20 22 37 20 36 32 39 20 493 52", "7 629
1010: 36 39 37 20 37 33 31 20 37 39 39 20 34 33 37 20 697 731 799 437
1020: 35 35 31 20 35 38 39 20 37 30 33 20 37 37 39 20 551 589 703 779
1030: 38 31 37 20 38 39 33 20 36 36 37 20 22 2c 20 22 817 893 667 ", "
1040: 37 31 33 20 38 35 31 20 39 34 33 20 39 38 39 20 713 851 943 989
1050: 31 30 38 31 20 38 39 39 20 31 30 37 33 20 31 31 1081 899 1073 11
1060: 38 39 20 31 32 34 37 20 31 33 36 33 20 31 31 34 89 1247 1363 114
1070: 37 20 22 2c 20 22 31 32 37 31 20 31 33 33 33 20 7 ", "1271 1333
1080: 31 34 35 37 20 31 35 31 37 20 31 35 39 31 20 31 1457 1517 1591 1
1090: 37 33 39 20 31 37 36 33 20 31 39 32 37 20 32 30 739 1763 1927 20
10a0: 32 31 20 31 31 38 30 33 22 2c 20 22 20 31 38 33 21 11803", " 183
10b0: 37 37 20 32 33 33 37 20 31 34 37 39 20 31 38 38 77 2337 1479 188
10c0: 36 20 34 39 34 35 20 34 31 39 39 20 37 31 32 39 6 4945 4199 7129
10d0: 39 20 36 32 33 35 20 32 34 36 20 39 38 32 22 2c 9 6235 246 982",
10e0: 20 22 33 20 34 39 32 31 20 38 35 36 39 20 31 34 "3 4921 8569 14
10f0: 30 35 33 20 31 36 38 31 33 20 33 31 34 38 37 20 053 16813 31487
1100: 31 37 37 31 39 20 31 34 32 36 20 32 31 30 39 20 17719 1426 2109
1110: 32 35 38 20 22 2c 20 22 31 36 39 36 37 20 32 32 258 ", "16967 22
1120: 36 30 37 20 31 33 32 34 33 20 32 30 30 31 20 34 607 13243 2001 4
1130: 34 39 35 20 33 30 35 39 20 32 35 35 33 20 34 34 495 3059 2553 44
1140: 30 33 20 31 35 39 38 20 33 35 22 2c 20 22 36 35 03 1598 35", "65
1150: 20 39 36 33 35 20 39 35 34 31 20 33 31 30 20 32 9635 9541 310 2
1160: 38 34 39 20 35 34 35 33 20 36 39 32 33 20 33 38 849 5453 6923 38
1170: 35 37 20 31 38 38 35 20 36 34 35 20 32 33 30 33 57 1885 645 2303
1180: 22 2c 20 22 20 31 34 36 36 33 20 33 36 38 35 39 ", " 14663 36859
1190: 20 36 37 32 31 20 36 35 38 20 32 30 39 31 20 31 6721 658 2091 1
11a0: 38 33 33 20 31 34 31 39 20 33 32 37 35 39 20 36 833 1419 32759 6
11b0: 38 34 31 33 20 33 22 2c 20 22 39 39 35 20 33 34 8413 3", "995 34
11c0: 38 39 31 20 35 35 38 38 33 20 32 32 33 33 20 35 891 55883 2233 5
11d0: 39 34 35 20 31 30 31 39 39 20 32 32 32 20 32 35 945 10199 222 25
11e0: 34 32 20 31 35 39 35 20 31 36 31 36 22 2c 20 22 42 1595 1616", "
11f0: 39 20 32 33 36 39 33 20 37 34 31 20 37 36 35 37 9 23693 741 7657
1200: 20 32 32 35 35 20 33 34 38 35 20 34 33 39 39 33 2255 3485 43993
1210: 20 34 31 32 33 20 34 30 35 34 39 20 32 36 33 38 4123 40549 2638
1220: 31 20 22 2c 20 22 32 34 36 35 20 34 31 39 37 31 1 ", "2465 41971
1230: 20 35 37 38 31 20 32 39 39 37 31 20 33 38 37 20 5781 29971 387
1240: 31 35 35 31 20 32 33 30 20 38 31 37 37 20 32 30 1551 230 8177 20
1250: 32 31 33 20 31 39 31 32 22 2c 20 22 39 20 31 34 213 1912", "9 14
1260: 34 33 20 32 32 32 33 31 20 37 35 36 37 20 31 31 43 22231 7567 11
1270: 33 33 39 20 38 38 39 37 20 36 32 37 20 36 33 38 339 8897 627 638
1280: 20 31 32 36 31 37 20 32 37 33 37 20 31 34 22 2c 12617 2737 14",
1290: 20 22 33 35 20 36 35 31 20 31 34 34 36 37 20 32 "35 651 14467 2
12a0: 30 35 33 39 20 39 38 37 20 35 32 31 37 20 31 32 0539 987 5217 12
12b0: 36 37 33 20 32 31 39 33 20 33 33 36 37 20 36 32 673 2193 3367 62
12c0: 36 35 31 20 22 2c 20 22 32 34 36 37 39 20 34 31 651 ", "24679 41
12d0: 38 20 31 38 36 20 31 32 31 32 31 20 35 31 31 37 8 186 12121 5117
12e0: 20 31 37 36 37 20 34 33 30 31 20 32 33 38 20 39 1767 4301 238 9
12f0: 38 38 39 20 31 37 39 38 20 38 22 2c 20 22 39 38 889 1798 8", "98
1300: 37 20 31 36 37 37 20 37 37 33 33 20 32 36 31 20 7 1677 7733 261
1310: 32 36 36 36 20 31 33 30 37 39 20 31 36 30 32 37 2666 13079 16027
1320: 20 31 30 33 34 20 31 35 34 37 20 33 30 33 34 20 1034 1547 3034
1330: 22 2c 20 22 31 37 30 38 31 20 38 30 32 39 20 32 ", "17081 8029 2
1340: 33 36 35 20 34 36 35 20 31 31 36 38 37 20 32 30 365 465 11687 20
1350: 36 38 33 20 37 35 20 31 33 37 31 37 20 33 34 35 683 75 13717 345
1360: 20 35 36 31 20 33 22 2c 20 22 39 39 39 37 20 35 561 3", "9997 5
1370: 34 32 33 20 37 34 32 39 20 32 38 36 38 31 20 31 423 7429 28681 1
1380: 34 31 34 37 20 32 39 32 33 33 20 33 36 31 39 20 4147 29233 3619
1390: 31 36 32 31 31 20 32 32 35 39 31 20 22 2c 20 22 16211 22591 ", "
13a0: 35 39 37 33 37 20 35 32 31 31 31 20 38 39 37 20 59737 52111 897
13b0: 32 34 38 36 33 20 35 37 39 37 20 33 34 34 38 31 24863 5797 34481
13c0: 20 32 36 36 20 31 35 35 38 20 33 37 34 20 31 30 266 1558 374 10
13d0: 36 31 22 2c 20 22 39 20 33 38 39 35 20 32 31 33 61", "9 3895 213
13e0: 39 20 31 37 30 32 20 32 36 33 39 20 31 33 39 34 9 1702 2639 1394
13f0: 20 31 34 32 31 20 32 36 33 35 20 31 30 32 20 34 1421 2635 102 4
1400: 31 34 37 20 33 36 38 39 22 2c 20 22 20 38 39 35 147 3689", " 895
1410: 39 20 34 32 39 20 32 38 35 20 32 37 36 38 33 20 9 429 285 27683
1420: 34 34 32 20 32 33 39 37 20 31 38 32 34 31 20 34 442 2397 18241 4
1430: 32 37 37 20 36 39 31 39 20 33 32 35 20 31 22 2c 277 6919 325 1",
1440: 20 22 34 39 39 33 20 32 37 38 33 20 31 30 36 36 "4993 2783 1066
1450: 20 33 34 35 31 20 32 30 33 38 37 20 36 36 30 31 3451 20387 6601
1460: 20 31 31 31 38 20 31 31 34 20 33 36 36 31 33 20 1118 114 36613
1470: 31 31 38 39 22 2c 20 22 31 20 31 35 30 35 20 35 1189", "1 1505 5
1480: 31 38 20 34 32 20 31 36 36 38 37 20 35 39 35 37 18 42 16687 5957
1490: 20 31 34 36 32 20 37 33 33 37 20 33 37 34 31 20 1462 7337 3741
14a0: 31 32 32 35 39 20 39 33 33 31 22 2c 20 22 20 32 12259 9331", " 2
14b0: 33 31 20 33 34 34 31 20 32 37 33 20 35 38 31 39 31 3441 273 5819
14c0: 20 31 38 34 39 31 20 34 37 30 20 31 35 39 39 20 18491 470 1599
14d0: 39 31 33 39 20 32 37 31 37 20 31 30 31 32 37 20 9139 2717 10127
14e0: 22 2c 20 22 31 36 35 33 20 32 37 35 35 20 32 34 ", "1653 2755 24
14f0: 39 34 20 35 37 33 35 20 39 30 36 31 20 37 30 35 94 5735 9061 705
1500: 20 38 37 34 20 36 35 32 33 31 20 31 35 31 38 31 874 65231 15181
1510: 20 31 37 37 31 20 22 2c 20 22 31 39 35 20 34 33 1771 ", "195 43
1520: 35 20 31 33 30 20 38 36 37 20 32 30 39 33 20 33 5 130 867 2093 3
1530: 33 34 39 37 20 32 39 35 36 33 20 31 38 32 20 33 3497 29563 182 3
1540: 33 30 34 31 20 34 38 37 39 20 36 36 22 2c 20 22 3041 4879 66", "
1550: 35 20 31 36 35 32 33 20 34 33 37 31 20 31 30 32 5 16523 4371 102
1560: 33 20 31 32 32 32 20 38 37 32 39 20 33 37 33 31 3 1222 8729 3731
1570: 20 35 35 39 33 20 31 33 31 31 20 34 37 31 35 20 5593 1311 4715
1580: 37 37 22 2c 20 22 37 20 33 37 30 20 39 33 35 20 77", "7 370 935
1590: 31 37 39 31 37 20 38 30 34 31 20 39 36 39 20 36 17917 8041 969 6
15a0: 36 36 35 20 34 30 38 39 20 32 34 30 33 37 20 31 665 4089 24037 1
15b0: 33 35 34 37 20 32 32 39 22 2c 20 22 34 20 36 31 3547 229", "4 61
15c0: 34 39 20 33 32 32 20 33 38 36 35 37 20 32 36 39 49 322 38657 269
15d0: 37 20 39 34 36 20 34 36 36 39 20 31 32 36 35 20 7 946 4669 1265
15e0: 33 38 33 39 39 20 36 33 35 35 20 31 30 30 22 2c 38399 6355 100",
15f0: 20 22 31 33 20 32 34 31 34 39 20 38 31 34 20 37 "13 24149 814 7
1600: 31 36 33 20 31 31 30 35 20 37 32 38 35 20 31 36 163 1105 7285 16
1610: 33 34 20 33 34 37 38 20 32 34 30 35 20 32 37 39 34 3478 2405 279
1620: 35 20 32 30 22 2c 20 22 36 37 37 20 32 31 36 32 5 20", "677 2162
1630: 20 31 37 38 36 20 36 30 39 20 33 31 33 34 39 20 1786 609 31349
1640: 34 38 30 37 20 31 30 36 32 31 20 31 38 38 20 36 4807 10621 188 6
1650: 34 36 20 36 34 30 39 20 31 37 22 2c 20 22 32 39 46 6409 17", "29
1660: 20 39 33 36 31 20 32 35 38 39 37 20 33 38 35 20 9361 25897 385
1670: 33 35 35 33 20 33 31 35 37 20 34 36 31 33 39 20 3553 3157 46139
1680: 31 39 37 38 20 31 30 35 20 34 36 34 38 33 20 31 1978 105 46483 1
1690: 22 2c 20 22 39 33 39 33 20 39 36 32 20 31 31 39 ", "9393 962 119
16a0: 35 31 20 33 30 32 32 39 20 35 33 36 32 31 20 33 51 30229 53621 3
16b0: 30 36 35 39 20 33 32 34 33 20 34 32 32 35 33 20 0659 3243 42253
16c0: 36 31 35 20 36 30 22 2c 20 22 32 20 32 35 33 32 615 60", "2 2532
16d0: 37 20 31 32 35 38 20 33 32 31 39 20 33 35 31 35 7 1258 3219 3515
16e0: 20 38 36 31 20 31 33 38 38 39 20 35 39 35 20 39 861 13889 595 9
16f0: 33 36 37 20 31 30 35 34 20 36 30 36 22 2c 20 22 367 1054 606", "
1700: 31 20 36 38 32 20 37 38 20 33 39 35 32 37 20 36 1 682 78 39527 6
1710: 32 39 33 20 38 36 39 35 20 34 32 33 20 36 37 32 293 8695 423 672
1720: 37 20 32 33 37 38 20 31 35 39 37 39 20 31 33 38 7 2378 15979 138
1730: 20 35 22 2c 20 22 32 38 39 20 38 33 32 33 20 31 5", "289 8323 1
1740: 30 31 35 20 38 33 33 20 32 31 37 39 33 20 35 36 015 833 21793 56
1750: 38 31 20 32 36 36 35 20 33 35 31 33 31 20 31 36 81 2665 35131 16
1760: 30 33 31 20 34 31 30 20 22 2c 20 22 31 30 35 38 031 410 ", "1058
1770: 20 35 38 36 33 20 31 32 39 35 20 32 30 31 35 20 5863 1295 2015
1780: 31 33 33 34 20 32 39 36 37 20 32 37 38 36 39 20 1334 2967 27869
1790: 31 35 32 38 33 20 36 30 36 33 20 31 32 33 22 2c 15283 6063 123",
17a0: 20 22 34 31 20 31 37 34 20 34 34 33 32 31 20 32 "41 174 44321 2
17b0: 34 37 36 39 20 31 32 34 20 31 36 31 35 20 33 33 4769 124 1615 33
17c0: 32 36 33 20 35 33 39 30 39 20 35 36 31 32 39 20 263 53909 56129
17d0: 31 31 31 33 22 2c 20 22 37 20 31 33 30 39 20 31 1113", "7 1309 1
17e0: 35 34 20 35 32 39 31 20 31 38 38 37 20 32 31 36 54 5291 1887 216
17f0: 30 37 20 31 33 35 38 33 20 37 36 36 37 20 31 31 07 13583 7667 11
1800: 30 36 33 20 39 35 30 33 20 34 22 2c 20 22 30 36 063 9503 4", "06
1810: 20 39 33 31 20 37 35 34 20 32 30 20 33 30 20 34 931 754 20 30 4
1820: 37 37 33 20 32 38 38 32 33 20 33 38 35 34 20 31 773 28823 3854 1
1830: 31 30 20 31 37 33 32 39 20 37 31 35 20 35 30 36 10 17329 715 506
1840: 22 2c 20 22 20 34 33 30 20 35 37 34 20 31 35 33 ", " 430 574 153
1850: 20 31 30 38 35 20 32 38 32 20 32 39 31 34 20 38 1085 282 2914 8
1860: 32 38 36 31 20 31 32 30 39 20 33 38 31 33 20 31 2861 1209 3813 1
1870: 34 36 33 20 31 31 22 2c 20 22 33 31 20 32 33 38 463 11", "31 238
1880: 37 20 32 31 34 36 20 31 30 31 30 35 20 34 35 35 7 2146 10105 455
1890: 31 20 35 37 31 39 20 37 35 38 35 20 31 33 35 33 1 5719 7585 1353
18a0: 20 33 36 35 35 20 33 30 35 35 20 31 22 2c 20 22 3655 3055 1", "
18b0: 32 32 31 20 32 30 33 35 20 32 32 31 30 33 20 39 221 2035 22103 9
18c0: 30 32 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 02"};... vector
18d0: 20 3c 73 74 72 69 6e 67 3e 20 73 70 65 63 69 61 <string> specia
18e0: 6c 28 73 70 65 63 69 61 6c 5f 2c 20 73 70 65 63 l(special_, spec
18f0: 69 61 6c 5f 2b 73 69 7a 65 6f 66 28 73 70 65 63 ial_+sizeof(spec
1900: 69 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 70 ial_)/sizeof(*sp
1910: 65 63 69 61 6c 5f 29 29 3b 20 0d 0a 09 6c 6f 6e ecial_)); ...lon
1920: 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 38 38 38 31 g long _ = 18881
1930: 31 33 35 36 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 7d 1356LL; ..END..}
1940: 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 52 ..// END CUT HER
1950: 45 0d 0a E..