最近教练让我们开始做欧拉计划了
所以正在写，发篇分享防止进度丢失
现在做到了第20题，但是交不了，不知道对不对
代码量不多，也就几百行
难道就没人写c++题解吗？
都是干货
附件在这里
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
typedef long long ll ;
int primes[2000010] ;
bool nums[20000010] ;
int cnt ;
void chkmax(int &a,int b) { if(a<b) a=b; }
void chkmin(int &a,int b) { if(a>b) a=b; }
void chkmax(ll &a,ll b) { if(a<b) a=b; }
void chkmin(ll &a,ll b) { if(a>b) a=b; }
void swap(int a,int b) { if(a!=b) a^=b^=a^=b; }
void rev(int a[],int l,int r) { for(int i=l,j=r;i<j;i++,j--) swap(a[i],a[j]); }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a*b/gcd(a,b); }
class bigint
{
public:
int val[100010],size ;
int at(int spt) { return val[spt]; }
void mdf(int spt,int v) { val[spt]=v; }
void push(int v) { mdf(++size,v); }
void pop() { size--; }
int back() { return val[size]; }
void reverse() { rev(val,1,size) ; }
bigint(int p) { for(;p;val[++size]=p%10,p/=10); reverse(); }
bigint() { size=0; }
bigint(bigint &a)
{
size=a.size ;
for(int i=1;i<=size;i++) val[i]=a.at(i) ;
}
void print()
{
if(!size) puts("0") ;
else
{
for(int i=size;i;i--) printf("%d",val[i]) ;
puts("") ;
}
}
int sum()
{
int ans=0 ;
for(int i=1;i<=size;i++) ans+=val[i] ;
return ans ;
}
bool operator < (bigint a)
{
if(size!=a.size) return size<a.size ;
for(int i=size;i;i--)
if(val[i]!=a.at(i)) return val[i]<a.at(i) ;
return false ;
}
bigint operator+ (bigint b)
{
if(*this<b) return b+*this ;
bigint c ;
reverse(),b.reverse() ;
int t=0 ;
for(int i=1;i<=size;i++)
{
t+=val[i] ;
if(i<=b.size) t+=b.at(i) ;
c.push(t%10) ;
t/=10 ;
}
if(t) c.push(t) ;
c.reverse() ;
return c ;
}
} ;
void init_prime()
{
for(int i=2;cnt<=100010;i++)
{
if(!nums[i]) primes[++cnt]=i ;
for(int j=1;primes[j]*i<=5e6;j++)
{
nums[primes[j]*i]=true ;
if(i%primes[j]==0) break ;
}
}
}
// #1:
// 如果我们将小于10的所有是3或5倍数的自然数列出来，\
我们得到3，5，6和9，它们的和是23。\
与之类似，计算1000以下所有是3或5的倍数的自然数的和。
int solve_1()
{
int sum=0 ;
for(int i=1;i<=1000;i++)
if(i%3==0&&i%5==0) sum+=i ;
return sum ;
}
// #2:
// 斐波那契序列中的数都是由前两项加总得出，假设第一与第二项为1与2，则前十项分别为：\
\
1，2，3，5，8，13，21，34，55，89 \
\
考虑不超过四百万的斐波那契数，计算其中偶数斐波那契数的和。
int solve_2()
{
int sum=0 ;
int a=0,b=0,c=1 ;
while(c<=4000000)
{
a=b,b=c,c=a+b ;
if(!(c&1)) sum+=c ;
}
return sum ;
}
// #3:
// 13195的质因数分别为5，7，13与29，600851475143最大的质因数是多少？
ll solve_3()
{
const ll d=600851475143 ;
for(ll i=2;;i++)
if(d%i==0) return d/i ;
return d ;
}
// #4:
// 回文数即从正反两边读都是一样的数， \
两个二位数的乘积中最大的回文数为9009=91∗99 \
寻找两个三位数乘积中最大的回文数。
int solve_4()
{
int res=0 ;
for(int i=999;i>=10;i--)
{
int j=999 ;
for(;j>=10;j--)
{
int t=i*j ;
int *d=new int[10] ;
int now=0 ;
for(;t;t/=10) d[++now]=t%10 ;
for(int p=1,q=now;p<q;p++,q--)
if(d[p]!=d[q]) goto fail ;
break ;
fail: delete[] d ;
}
if(i*999<=res) return res ;
else if(res<=i*j) res=i*j ;
}
return res ;
}
// #5:
// 2520是可以被从一到十所有自然数整除的最小的数 \
即为从一到十的自然数的最小公倍数 \
求从一到二十所有自然数的最小公倍数。
ll solve_5()
{
ll ans=1 ;
for(int i=1;i<=20;i+=2) ans=lcm(ans,i*(i+1)) ;
return ans ;
}
// #6:
// 前十个自然数的平方的和为： \
1^2+2^2+3^2+...+10^2=385 \
而前十个自然数和的平方为：\
(1+2+3+...+10)^2=55^2=3025 \
两者的差为3025−385=2640 \
求前一百个自然数的和的平方与平方的和之间的差值。
int solve_6()
{
int res1=0,res2=0 ;
for(int i=1;i<=100;i++) res1+=i ; res1*=res1 ;
for(int i=1;i<=100;i++) res2+=i*i ;
return res1-res2 ;
}
// #7:
// 列出前六个质数，我们可以发现第六个质数为13，那么第10001个质数是多少？
int solve_7() { return primes[10001]; }
ll solve_8()
{
char ch[]=
"73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450" ;
ll res=0 ;
for(int i=0;i+13<1000;i++)
{
ll ans=1 ;
for(int j=i;j<i+13;j++)
if(ch[j]=='0') { i=j+1; goto out; }
else ans*=ch[j]&15 ;
chkmax(res,ans) ;
out: continue ;
}
return res ;
}
// #7:
// 毕达哥拉斯三元数是指一类三个自然数的集合 \
其中a<b<c且a^2+b^2=c^2 \
例如3^2+4^2=5^2 \
仅存在一组毕达哥拉斯三元数使得\
\
a+b+c=1000 \
\
求abc。
int solve_9()
{
for(int i=1;i<=333;i++)
for(int j=i;j<=1000-i-j;j++)
{
int k=1000-i-j ;
if(i*i+j*j==k*k) return i*j*k ;
}
return -1 ;
}
// #10:
// 求所有两百万以下的质数的和
ll solve_10()
{
ll ans=0 ;
for(int i=1;primes[i]<=2e6;i++) ans+=primes[i] ;
return ans ;
}
// #11:
// 求在这个网格中，同一方向(上、下、左、右以及对角线)相邻四个元素最大乘积。
int solve_11()
{
int arr[20][20]=
{
{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91,8 },
{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62,0 },
{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
{52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
{24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
{67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
{24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
{21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
{78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
{16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
{86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
{19,80,81,68,5 ,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
{4 ,52,8 ,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
{88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
{4 ,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
{20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
{1 ,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48},
} ;
int ans=0 ;
for(int i=0;i+4<20;i++)
for(int j=0;j<20;j++)
chkmax(ans,arr[i][j]*arr[i+1][j]*arr[i+2][j]*arr[i+3][j]) ;
for(int i=0;i<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i][j+1]*arr[i][j+2]*arr[i][j+3]) ;
for(int i=0;i+4<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3]) ;
for(int i=4;i<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i-1][j+1]*arr[i-2][j+2]*arr[i-3][j+3]) ;
return ans ;
}
// #12:
// 三角数即由依次排列的自然数的和构成 \
所以第7个三角数是1+2+3+4+5+6+7=28 \
前十个三角数是：1,3,6,10,15,21,28,36,45,55,... \
让我们列出前七个三角数的因子：
// 1:1 \
// 3:1,3 \
// 6:1,2,3,6 \
// 10:1,2,5,10 \
// 15:1,3,5,15 \
// 21:1,3,7:21 \
// 28:1,2,4,7,14,28 \
可以看出28是第一个因子超过5的三角数 \
求第一个因子超过五百万的三角数。
ll solve_12()
{
int arr[2][1010]={{0}} ;
int maxv=2 ;
const int limit=5e6 ;
for(int i=1;;i++)
{
bool now=i&1,prev=!(i&1) ;
int j=i ;
for(int k=2;k<=j/k;k++)
if(j%k==0)
{
while(j%k==0) j/=k,arr[now][k]++ ;
if(maxv<k) maxv=k ;
}
arr[now][j]++ ;
if(i==limit) continue ;
int val=1 ;
for(int k=2;k<=maxv;k++)
{
int t=arr[prev][k]+arr[now][k] ;
if(k==2) t-- ;
val*=t+1 ;
}
if(val>=limit) return i*(i-1)/2 ;
}
return -1 ;
}
// #13:
// 计算如下一百个50位数的和，求这个和的前十位数。
ll solve_13()
{
ll ans=
(ll) 371072875339021+
(ll) 463769376774900+
(ll) 743249861995247+
(ll) 919422133635741+
(ll) 230675882075393+
(ll) 892616706966236+
(ll) 281128798128499+
(ll) 442742289174325+
(ll) 474514457360013+
(ll) 703864861058430+
(ll) 621764571418565+
(ll) 649063524627419+
(ll) 925758677183372+
(ll) 582035653253593+
(ll) 801811993848262+
(ll) 353986643728271+
(ll) 865155060062958+
(ll) 716938887077154+
(ll) 543700705768266+
(ll) 532826541087568+
(ll) 361232725250002+
(ll) 458765761724109+
(ll) 174237069058518+
(ll) 811426604180868+
(ll) 519343254517283+
(ll) 624672216484350+
(ll) 157324443869081+
(ll) 550376875256787+
(ll) 183363848253301+
(ll) 803862875928784+
(ll) 781828337579931+
(ll) 167263201004368+
(ll) 484030981290777+
(ll) 870869875513927+
(ll) 599594068957565+
(ll) 697939506796526+
(ll) 410526847082990+
(ll) 653786073615010+
(ll) 358290353174347+
(ll) 949537597651053+
(ll) 889028025717332+
(ll) 252676802760780+
(ll) 362702185404977+
(ll) 240744869082311+
(ll) 914302881971032+
(ll) 344130655780161+
(ll) 230530811728164+
(ll) 114876969321549+
(ll) 637832994906362+
(ll) 677201869716985+
(ll) 955482553002635+
(ll) 760853271322857+
(ll) 377742425354112+
(ll) 237019132757256+
(ll) 297988602722583+
(ll) 184957014548792+
(ll) 382982037830314+
(ll) 348295438291999+
(ll) 409579530664052+
(ll) 297461521855023+
(ll) 416981162220729+
(ll) 624679571944012+
(ll) 231897067725479+
(ll) 861880882258753+
(ll) 113067397083047+
(ll) 829591747671403+
(ll) 976233310448183+
(ll) 428462801835170+
(ll) 551216035469812+
(ll) 322381957343293+
(ll) 755061649651847+
(ll) 621778427521926+
(ll) 329241857071473+
(ll) 995186714302352+
(ll) 732674608005915+
(ll) 768418225246744+
(ll) 971426179103425+
(ll) 877836461827993+
(ll) 108488025216746+
(ll) 713296124747824+
(ll) 621840735723997+
(ll) 666278919814880+
(ll) 606618262936828+
(ll) 857869440895529+
(ll) 660243964099053+
(ll) 649139826800329+
(ll) 167309393198727+
(ll) 948093772450487+
(ll) 786391670211874+
(ll) 153687137119366+
(ll) 407899231155355+
(ll) 448899115014406+
(ll) 415031288803395+
(ll) 812348806732101+
(ll) 826165707739483+
(ll) 229188020587773+
(ll) 771585425020165+
(ll) 721078384350691+
(ll) 208496039801340+
(ll) 535035342264725 ;
int p=0 ;
for(ll ts=ans;ts;ts/=10,p++) ;
for(int i=1;i<=p-10;i++) ans/=10 ;
return ans ;
}
// #14:
// 对于所有正整数，考虑如下迭代序列： \
n → n/2 if n is even \
n → 3n+1 if n is odd \
从13开始并使用以上迭代规则，我们可以得到以下序列：\
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 \
可以看出这个序列从13开始并到1结束总共包含10个数 \
考拉兹猜想指出使用以上迭代规则，所有正整数都会最终回到一 \
求在一百万以下，那个起始数可以产生最长的考拉兹序列？ \
(注意：序列中包含的数的个数可以超过一百万。)
int f[2000010] ;
bool vis[2000010] ;
int stk[2000010],top ;
int solve_14()
{
stk[top++]=1 ;
int ans=0 ;
while(top)
{
int t=stk[--top] ;
if(t>=1e6) continue ;
else if(vis[t]) continue ;
vis[t]=true ;
f[t<<1]=f[t]+1,stk[top++]=t<<1 ;
if(t%3==1) f[t/3]=f[t]+1,stk[top++]=t/3 ;
chkmax(ans,f[t]+1) ;
}
return ans ;
}
// #15:
// 在一个2×2的栅格中，从左上角出来，只能向右或向下移动，总共有6条路径可以到达栅格的右下角;
// 求在一个20×20的栅格中，有多少条移动路径？
ll solve_15()
{
ll ans=1 ;
for(int i=21;i<=40;i++) ans*=i,ans/=(i-20) ;
return ans ;
}
// #16:
// 2^15=32768且各位数之和为3+2+7+6+8=26 \
求2^1000各位数之和。
int solve_16()
{
bigint res(1) ;
for(int i=1;i<=1000;i++) res=res+res ;
return res.sum() ;
}
// #17:
// 如果把数字一到五用单词写出来，即one, two, three, four, five，那么总共使用的字母数量：\
3+3+5+4+4=19 \
如果把从一到一千的数字用对应的单词写出来，总共需要多少个字母？ \
注意：不要计算空格与连字符 \
如342(three hundred and forty-two)包含23个字母 \
而115(one hundred and fifteen)包含20个字母 \
and的使用遵守英式英语的规则。
const int nwords []={0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,9,9,8,6} ;
const int plwords[]={0,0,6,6,5,5,5,7,6,5} ;
int wordcnt(int x)
{
if(x<=20) return nwords[x] ;
else if(x<100) return plwords[x/10]+nwords[x%10] ;
else return nwords[x/100]+10+wordcnt(x%100) ;
}
int solve_17()
{
int res=0 ;
for(int i=1;i<=1000;i++) res+=wordcnt(i) ;
return res ;
}
// #19:
// 1900/1/1~2000/12/31 每个月的首日是星期天的次数是多少？
bool leap(int y)
{
if(y&3) return false ;
else if(y%100) return true ;
else return y%400==0 ;
}
void dateinc(int &ans,int &week,int &year)
{
if(leap(year)) week+=366 ;
else week+=365 ;
week%=7,year++ ;
if(!week) ans++ ;
}
int solve_19()
{
int ans=0 ;
for(int w=1,y=1900;y<=2000;dateinc(ans,w,y)) ;
return ans ;
}
// #20:
// 求100!各位数之和
int solve_20()
{
bigint res(1) ;
for(int i=1;i<=100;i++)
{
bigint backup(res) ;
for(int j=1;j<i;j++) res=res+backup ;
}
return res.sum() ;
}
int main()
{
init_prime() ;
printf("%d\n",solve_1()) ;
printf("%d\n",solve_2()) ;
printf("%lld\n",solve_3()) ;
printf("%d\n",solve_4()) ;
printf("%lld\n",solve_5()) ;
printf("%d\n",solve_6()) ;
printf("%d\n",solve_7()) ;
printf("%lld\n",solve_8()) ;
printf("%d\n",solve_9()) ;
printf("%lld\n",solve_10()) ;
printf("%d\n",solve_11()) ;
printf("%lld\n",solve_12()) ;
printf("%lld\n",solve_13()) ;
printf("%d\n",solve_14()) ;
printf("%lld\n",solve_15()) ;
printf("%d\n",solve_16()) ;
printf("%d\n",solve_17()) ;
printf("%d\n",solve_19()) ;
printf("%d\n",solve_20()) ;
return 0 ;
}
纯净版
#include <cstdio>
typedef long long ll ;
int primes[2000010] ;
bool nums[20000010] ;
int cnt ;
void chkmax(int &a,int b) { if(a<b) a=b; }
void chkmin(int &a,int b) { if(a>b) a=b; }
void chkmax(ll &a,ll b) { if(a<b) a=b; }
void chkmin(ll &a,ll b) { if(a>b) a=b; }
void swap(int a,int b) { if(a!=b) a^=b^=a^=b; }
void rev(int a[],int l,int r) { for(int i=l,j=r;i<j;i++,j--) swap(a[i],a[j]); }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a*b/gcd(a,b); }
class bigint
{
public:
int val[100010],size ;
int at(int spt) { return val[spt]; }
void mdf(int spt,int v) { val[spt]=v; }
void push(int v) { mdf(++size,v); }
void pop() { size--; }
int back() { return val[size]; }
void reverse() { rev(val,1,size) ; }
bigint(int p) { for(;p;val[++size]=p%10,p/=10); reverse(); }
bigint() { size=0; }
bigint(bigint &a)
{
size=a.size ;
for(int i=1;i<=size;i++) val[i]=a.at(i) ;
}
void print()
{
if(!size) puts("0") ;
else
{
for(int i=size;i;i--) printf("%d",val[i]) ;
puts("") ;
}
}
int sum()
{
int ans=0 ;
for(int i=1;i<=size;i++) ans+=val[i] ;
return ans ;
}
bool operator < (bigint a)
{
if(size!=a.size) return size<a.size ;
for(int i=size;i;i--)
if(val[i]!=a.at(i)) return val[i]<a.at(i) ;
return false ;
}
bigint operator+ (bigint b)
{
if(*this<b) return b+*this ;
bigint c ;
reverse(),b.reverse() ;
int t=0 ;
for(int i=1;i<=size;i++)
{
t+=val[i] ;
if(i<=b.size) t+=b.at(i) ;
c.push(t%10) ;
t/=10 ;
}
if(t) c.push(t) ;
c.reverse() ;
return c ;
}
} ;
void init_prime()
{
for(int i=2;cnt<=100010;i++)
{
if(!nums[i]) primes[++cnt]=i ;
for(int j=1;primes[j]*i<=5e6;j++)
{
nums[primes[j]*i]=true ;
if(i%primes[j]==0) break ;
}
}
}
int solve_1()
{
int sum=0 ;
for(int i=1;i<=1000;i++)
if(i%3==0&&i%5==0) sum+=i ;
return sum ;
}
int solve_2()
{
int sum=0 ;
int a=0,b=0,c=1 ;
while(c<=4000000)
{
a=b,b=c,c=a+b ;
if(!(c&1)) sum+=c ;
}
return sum ;
}
ll solve_3()
{
const ll d=600851475143 ;
for(ll i=2;;i++)
if(d%i==0) return d/i ;
return d ;
}
int solve_4()
{
int res=0 ;
for(int i=999;i>=10;i--)
{
int j=999 ;
for(;j>=10;j--)
{
int t=i*j ;
int *d=new int[10] ;
int now=0 ;
for(;t;t/=10) d[++now]=t%10 ;
for(int p=1,q=now;p<q;p++,q--)
if(d[p]!=d[q]) goto fail ;
break ;
fail: delete[] d ;
}
if(i*999<=res) return res ;
else if(res<=i*j) res=i*j ;
}
return res ;
}
ll solve_5()
{
ll ans=1 ;
for(int i=1;i<=20;i+=2) ans=lcm(ans,i*(i+1)) ;
return ans ;
}
int solve_6()
{
int res1=0,res2=0 ;
for(int i=1;i<=100;i++) res1+=i ; res1*=res1 ;
for(int i=1;i<=100;i++) res2+=i*i ;
return res1-res2 ;
}
int solve_7() { return primes[10001]; }
ll solve_8()
{
char ch[]=
"73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450" ;
ll res=0 ;
for(int i=0;i+13<1000;i++)
{
ll ans=1 ;
for(int j=i;j<i+13;j++)
if(ch[j]=='0') { i=j+1; goto out; }
else ans*=ch[j]&15 ;
chkmax(res,ans) ;
out: continue ;
}
return res ;
}
int solve_9()
{
for(int i=1;i<=333;i++)
for(int j=i;j<=1000-i-j;j++)
{
int k=1000-i-j ;
if(i*i+j*j==k*k) return i*j*k ;
}
return -1 ;
}
ll solve_10()
{
ll ans=0 ;
for(int i=1;primes[i]<=2e6;i++) ans+=primes[i] ;
return ans ;
}
int solve_11()
{
int arr[20][20]=
{
{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91,8 },
{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62,0 },
{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
{52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
{24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
{67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
{24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
{21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
{78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
{16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
{86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
{19,80,81,68,5 ,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
{4 ,52,8 ,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
{88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
{4 ,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
{20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
{1 ,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48},
} ;
int ans=0 ;
for(int i=0;i+4<20;i++)
for(int j=0;j<20;j++)
chkmax(ans,arr[i][j]*arr[i+1][j]*arr[i+2][j]*arr[i+3][j]) ;
for(int i=0;i<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i][j+1]*arr[i][j+2]*arr[i][j+3]) ;
for(int i=0;i+4<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3]) ;
for(int i=4;i<20;i++)
for(int j=0;j+4<20;j++)
chkmax(ans,arr[i][j]*arr[i-1][j+1]*arr[i-2][j+2]*arr[i-3][j+3]) ;
return ans ;
}
ll solve_12()
{
int arr[2][1010]={{0}} ;
int maxv=2 ;
const int limit=5e6 ;
for(int i=1;;i++)
{
bool now=i&1,prev=!(i&1) ;
int j=i ;
for(int k=2;k<=j/k;k++)
if(j%k==0)
{
while(j%k==0) j/=k,arr[now][k]++ ;
if(maxv<k) maxv=k ;
}
arr[now][j]++ ;
if(i==limit) continue ;
int val=1 ;
for(int k=2;k<=maxv;k++)
{
int t=arr[prev][k]+arr[now][k] ;
if(k==2) t-- ;
val*=t+1 ;
}
if(val>=limit) return i*(i-1)/2 ;
}
return -1 ;
}
ll solve_13()
{
ll ans=(ll) 371072875339021+(ll)463769376774900+(ll) 743249861995247+(ll) 919422133635741+
(ll) 230675882075393+(ll)892616706966236+(ll) 281128798128499+(ll) 442742289174325+
(ll) 474514457360013+(ll)703864861058430+(ll) 621764571418565+(ll) 649063524627419+
(ll) 925758677183372+(ll)582035653253593+(ll) 801811993848262+(ll) 353986643728271+
(ll) 865155060062958+(ll)716938887077154+(ll) 543700705768266+(ll) 532826541087568+
(ll) 361232725250002+(ll)458765761724109+(ll) 174237069058518+(ll) 811426604180868+
(ll) 519343254517283+(ll)624672216484350+(ll) 157324443869081+(ll) 550376875256787+
(ll) 183363848253301+(ll)803862875928784+(ll) 781828337579931+(ll) 167263201004368+
(ll) 484030981290777+(ll)870869875513927+(ll) 599594068957565+(ll) 697939506796526+
(ll) 410526847082990+(ll)653786073615010+(ll) 358290353174347+(ll) 949537597651053+
(ll) 889028025717332+(ll)252676802760780+(ll) 362702185404977+(ll) 240744869082311+
(ll) 914302881971032+(ll)344130655780161+(ll) 230530811728164+(ll) 114876969321549+
(ll) 637832994906362+(ll)677201869716985+(ll) 955482553002635+(ll) 760853271322857+
(ll) 377742425354112+(ll)237019132757256+(ll) 297988602722583+(ll) 184957014548792+
(ll) 382982037830314+(ll)348295438291999+(ll) 409579530664052+(ll) 297461521855023+
(ll) 416981162220729+(ll)624679571944012+(ll) 231897067725479+(ll) 861880882258753+
(ll) 113067397083047+(ll)829591747671403+(ll) 976233310448183+(ll) 428462801835170+
(ll) 551216035469812+(ll)322381957343293+(ll) 755061649651847+(ll) 621778427521926+
(ll) 329241857071473+(ll)995186714302352+(ll) 732674608005915+(ll) 768418225246744+
(ll) 971426179103425+(ll)877836461827993+(ll) 108488025216746+(ll) 713296124747824+
(ll) 621840735723997+(ll)666278919814880+(ll) 606618262936828+(ll) 857869440895529+
(ll) 660243964099053+(ll)649139826800329+(ll) 167309393198727+(ll) 948093772450487+
(ll) 786391670211874+(ll)153687137119366+(ll) 407899231155355+(ll) 448899115014406+
(ll) 415031288803395+(ll)812348806732101+(ll) 826165707739483+(ll) 229188020587773+
(ll) 771585425020165+(ll)721078384350691+(ll) 208496039801340+(ll) 535035342264725;
int p=0 ;
for(ll ts=ans;ts;ts/=10,p++) ;
for(int i=1;i<=p-10;i++) ans/=10 ;
return ans ;
}
int f[2000010] ;
bool vis[2000010] ;
int stk[2000010],top ;
int solve_14()
{
stk[top++]=1 ;
int ans=0 ;
while(top)
{
int t=stk[--top] ;
if(t>=1e6) continue ;
else if(vis[t]) continue ;
vis[t]=true ;
f[t<<1]=f[t]+1,stk[top++]=t<<1 ;
if(t%3==1) f[t/3]=f[t]+1,stk[top++]=t/3 ;
chkmax(ans,f[t]+1) ;
}
return ans ;
}
ll solve_15()
{
ll ans=1 ;
for(int i=21;i<=40;i++) ans*=i,ans/=(i-20) ;
return ans ;
}
int solve_16()
{
bigint res(1) ;
for(int i=1;i<=1000;i++) res=res+res ;
return res.sum() ;
}
const int nwords []={0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,9,9,8,6} ;
const int plwords[]={0,0,6,6,5,5,5,7,6,5} ;
int wordcnt(int x)
{
if(x<=20) return nwords[x] ;
else if(x<100) return plwords[x/10]+nwords[x%10] ;
else return nwords[x/100]+10+wordcnt(x%100) ;
}
int solve_17()
{
int res=0 ;
for(int i=1;i<=1000;i++) res+=wordcnt(i) ;
return res ;
}
bool leap(int y)
{
if(y&3) return false ;
else if(y%100) return true ;
else return y%400==0 ;
}
void dateinc(int &ans,int &week,int &year)
{
if(leap(year)) week+=366 ;
else week+=365 ;
week%=7,year++ ;
if(!week) ans++ ;
}
int solve_19()
{
int ans=0 ;
for(int w=1,y=1900;y<=2000;dateinc(ans,w,y)) ;
return ans ;
}
int solve_20()
{
bigint res(1) ;
for(int i=1;i<=100;i++)
{
bigint backup(res) ;
for(int j=1;j<i;j++) res=res+backup ;
}
return res.sum() ;
}
int main()
{
init_prime() ;
printf("%d\n",solve_1()) ;
printf("%d\n",solve_2()) ;
printf("%lld\n",solve_3()) ;
printf("%d\n",solve_4()) ;
printf("%lld\n",solve_5()) ;
printf("%d\n",solve_6()) ;
printf("%d\n",solve_7()) ;
printf("%lld\n",solve_8()) ;
printf("%d\n",solve_9()) ;
printf("%lld\n",solve_10()) ;
printf("%d\n",solve_11()) ;
printf("%lld\n",solve_12()) ;
printf("%lld\n",solve_13()) ;
printf("%d\n",solve_14()) ;
printf("%lld\n",solve_15()) ;
printf("%d\n",solve_16()) ;
printf("%d\n",solve_17()) ;
printf("%d\n",solve_19()) ;
printf("%d\n",solve_20()) ;
return 0 ;
}
