欧拉之路

Prime digit replacements

枚举每一位放数字还是放未知的，如果为止的就拿1代替单独存

因为要有8个，所以我们可知未知的一定是三的倍数，末尾一定是1,3,7，然后暴力搞一搞（剪枝跑得飞快）

 1 #include<bits/stdc++.h>
 2 #define reg register
 3 #define int long long
 4 using namespace std;
 5 int last[3]={1,3,7};
 6 bool check(int x){//判断素数 
 7     if(x==1||(x%6!=1&&x%6!=5))
 8         return 0;
 9     if(x==2||x==3)return 1;
10     int MAX=sqrt(x);
11     for(int i=5;i<=MAX;i+=6)
12         if(x%i==0||x%(i+2)==0)
13             return 0;
14     return 1;
15 }
16 void dfs(int k,int unknow,int know,int rest){//第几位 未知的放的位置 已知的 还剩几个未知的 
17     if(k-1<rest)return;//最后一位不放未知的 
18     if(k==1){
19         for(int p=0;p<3;p++){//枚举最后一位 
20             int f=0,ans=0;
21             for(reg int i=0;i<=9;i++)
22             if(check((know+unknow*i)*10+last[p])){
23                 if(unknow>know&&i==0)ans--;
24                 ans++;
25                 if(!f)f=(know+unknow*i)*10+last[p];
26                 if(ans+(9-i)<8)break; //如果剩下全是还没有8个就退出 
27             }
28             if(ans==8){//输出答案 
29                 printf("%d
",f);
30                 exit(0);
31             }
32             f=0,ans=0;
33         }
34         return;
35     }
36     for(reg int i=0;i<=9;i++)
37         dfs(k-1,unknow*10,know*10+i,rest);//继续搜索 
38     dfs(k-1,unknow*10+1,know*10,rest-1);
39     return;
40 }
41 signed main(){
42     for(reg int k=1;;k++){
43         for(reg int l=3;l<k;l+=3)
44             dfs(k,0,0,l);
45     }
46     return 0;
47 }

Permuted multiples

可以看出，125874和它的两倍251748拥有同样的数字，只是排列顺序不同。

有些正整数x满足2x、3x、4x、5x和6x都拥有相同的数字，求其中最小的正整数。

可知$x,6x$位数相同，所以加一个小小的剪枝，然后暴力判断

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int n=1e5;
 5 bool check(int x){
 6     int a=x,f=0;
 7     while(a){
 8         f+=pow(10,a%10);
 9         a/=10;
10     }
11     for(int i=2;i<=6;i++)
12     {
13         a=x*i;
14         int ff=0;
15         while(a){
16             ff+=pow(10,a%10);
17             a/=10;
18         }
19         if(ff!=f)return false;
20     }
21     return true;
22 }
23 signed main()
24 {
25     while(1){
26         for(int i=n;i*6<n*10;i++){
27             if(check(i)){
28                 printf("%d
",i);
29                 goto ed;
30             }
31         }
32             
33         n*=10;
34     }
35     ed:
36     return 0;
37 }

Combinatoric selections

首先你得知道$inom{n}{r}=inom{n}{n-r}=frac{n!}{r!(n-r)!}$

当$rleq lfloor frac{n}{2} floor$时，这个值是不会下降的，然后找到递推式

然后找到最大的直接计算就行了

Lychrel numbers

暴力stringstream转换然后判断回文即可

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int ans,tag;
 5 bool check(int x){
 6     for(int i=1;i<=60;i++){
 7         bool f=1;
 8         int nt=0;
 9         stringstream ss;
10         string s;
11         ss<<x;
12         ss>>s;
13         int len=s.size()-1;
14         for(int i=0;i<=len;i++){
15             nt=nt*10+s[i]+s[len-i]-'0'-'0';
16             if(s[i]!=s[len-i])f=0;
17         }
18         if(f&&i!=1){
19             return f;
20         }
21         x=nt;
22     }
23     return false;
24 }
25 signed main(){
26     for(tag=1;tag<=10000;tag++){
27         if(!check(tag))ans++;
28     }
29     printf("%d",ans);
30     return 0;
31 }