持续颓废更新中
\(Project\ Euler--\)一个数学题网站，以提交答案为主。
上面有一些不错的数学题，可以锻炼思维。
此篇博客用于记录\(PE\)上的刷题记录。
NO.1 Multiples of 3 and 5
题意：求出\(\sum_{i=1}^{999}i\)，满足\(3|i\)或\(5|i\)。
那么暴力循环判断即可。
代码：
\(Answer:233168\)
#includeint Sum;int main(){ for(int i=1;i<=999;++i) if(i%3==0||i%5==0) Sum+=i; printf("%d\n",Sum); return 0;}
NO.51 Prime digit replacements
首先筛一波素数，猜测答案不会太大，取上限\(10^6\)。
接着对素数暴力判断，因为要置换出\(8\)个素数，所以选择换的数一定\(\le 2\)。
然后就是暴力模拟了。
\(Answer:121313\)
#include#include int Ps[100005],Pn;int Num[15],Len;//分解的数字bool Cho[15];//是否置换bool v[1000005];const int Top=1000000;bool DFS(int p,int o){ if(p>Len) { int Cnt=0; for(int i=1;i<=Len;++i) if(Cho[i]) ++Cnt; if(!Cnt)return false; Cnt=0; for(int i=o;i<=9;++i) { int Wn=0; for(int j=Len;j>=1;--j) if(Cho[j])Wn=Wn*10+i; else Wn=Wn*10+Num[j]; if(!v[Wn])++Cnt; } return Cnt==8; } if(Num[p]==o) { Cho[p]=true; if(DFS(p+1,o))return true; } Cho[p]=false; return DFS(p+1,o);}bool Check(int x){ Len=0; while(x)Num[++Len]=x%10,x/=10; bool Flag=true; for(int i=1;i<=Len;++i) if(Num[i]<=2) Flag=false; if(Flag)return false; for(int i=0;i<=2;++i) if(DFS(1,i)) return true; return false;}int main(){ for(int i=2;i<=Top;++i) { if(!v[i])Ps[++Pn]=i; if(i<=Top/i) for(int j=i*i;j<=Top;j+=i) v[j]=true; } for(int i=1;i<=Pn;++i) if(Check(Ps[i])) return printf("%d\n",Ps[i]),0;}
NO.60 Prime pair sets
假设上限\(10^4\)。
先筛素数，预处理每两个可以连接的素数，暴搜即可。
\(Answer:26033\)
#include#include #include inline bool Prime(int x){ for(int i=2;i*i<=x;++i) if(x%i==0) return false; return true;}const int Top=10000;int Ans=0x3f3f3f3f,Cho[10];int Ps[Top+5],Pn;bool v[Top+5];std::vector g[Top+5];inline bool Acon(int a,int b){ int l1=1,l2=1; for(int i=a;i;i/=10)l1*=10; for(int i=b;i;i/=10)l2*=10; return Prime(a*l2+b)&&Prime(b*l1+a);}void DFS(int Cnt,int Sum){ if(Sum>=Ans)return; if(Cnt==6)return void(Ans=Sum); if(Sum+Ps[Cho[Cnt-1]]>=Ans)return; for(int i=0;i<(int)g[Cho[Cnt-1]].size();++i) { int Next=g[Cho[Cnt-1]][i]; bool Flag=true; for(int j=1;j