7-4 天长地久 (20 分)

“天长地久数”是指一个 K 位正整数 A，其满足条件为：A 的各位数字之和为 m，A+1 的各位数字之和为 n，且 m 与 n 的最大公约数是一个大于 2 的素数。本题就请你找出这些天长地久数。

输入格式：

输入在第一行给出正整数 N（≤5），随后 N 行，每行给出一对 K（3<K<10）和 m（1<m<90），其含义如题面所述。

输出格式：

对每一对输入的 K 和 m，首先在一行中输出 Case X，其中 X 是输出的编号（从 1 开始）；然后一行输出对应的 n 和 A，数字间以空格分隔。如果解不唯一，则每组解占一行，按 n 的递增序输出；若仍不唯一，则按 A 的递增序输出。若解不存在，则在一行中输出 No Solution。

输入样例：

2

6 45

7 80

输出样例：

Case 1

10 189999

10 279999

10 369999

10 459999

10 549999

10 639999

10 729999

10 819999

10 909999

Case 2

No Solution

命题人姥姥说了。。暴力就好了

自己浅薄的分析一下，如果数字尾数不是9，是其他的 ，那么+1之后

只能从类似的 123变成124，和从6变成7（举的例子）

也就是gcd(n+1,n)只能是0；

但是如果尾号是9

+1 之后变成0，前面进位

就是19 变20 和从 10变成2，也就是-9+1，尾数有几个连续的9就是减去几个9，然后进位再加一

只有尾数是9才能满足和的公约数不是1.

然后看几个9呢 。

一个九就是gcd（n+8，n）=8；不满足

俩九就是 gcd（n+17，n）=17；满足大于2了

后面可以再考虑进去多个九，已经不重要了，范围从3到9位去掉后面固定99，就剩下 1-7位了，前面直接遍历应该就稳稳的了

 

猜测的代码（现在还不能再pta上做真题，所以不知道对不对）

在原来超时的基础上，修改一下循环头

for(long long int l=p/10+99;l<p;l=l+100)

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b){if(b>a){int t=a;a=b;b=t;}if(b!=0){gcd(b,a%b);	}else{return a;}
}
int issu(int a){int b=2;for(b;b<=sqrt(a);b++){if(a%b==0){return 0;}}return 1;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cout<<"Case "<<i<<endl;int k,m;cin>>k>>m;if(m/k>9||k>=10||k<=3){cout<<"No Solution"<<endl;continue;}long long int p=1;for(long long int l=0;l<k;l++){p*=10;}int n1=0,n2=0;int flag=0;long long int s1,s2;for(long long int l=p/10+99;l<p;l=l+100){n1=0;n2=0;s1=l;s2=l+1;while(s1>0){n1+=s1%10;s1/=10;}//cout<<n1<<endl;if(n1!=m){continue;}while(s2>0){n2+=s2%10;s2/=10;}int pp=gcd(n1,n2);if(pp>2&&issu(pp)){flag=1;cout<<n2<<" "<<l<<endl;}}if(flag==0){cout<<"No Solution"<<endl;}}return 0;
}

 

 

 

10分15毫秒版

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct daan{string A;int n;};
bool cmp(daan d1,daan d2){//return (d1.A!=d2.A) ?d1.A<d2.A:d1.n<d2.n;return d1.A<d2.A;
}
daan da[1000000];
int gcd(int a,int b){if(b>a){int t=a;a=b;b=t;}if(b!=0){gcd(b,a%b);	}else{return a;}
}
int issu(int a){int b;for(b=2;b<=sqrt(a);b++){if(a%b==0){return 0;}}return 1;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cout<<"Case "<<i<<endl;int k,m;cin>>k>>m;if(m/k>9||k>=10||k<=3){cout<<"No Solution"<<endl;continue;}int n1=1;int flag=0;while(n1<=m){int p=gcd(m,n1);if(p>2&&issu(p)&&(m+1-n1)%9==0){int jiu=(m+1-n1)/9;int sheng=m-jiu*9;string s;for(int e=0;e<jiu;e++){s+='9';}//cout<<s<<endl;long long int p=1;for(int l=0;l<k-jiu;l++){p*=10;}for( long long int l=p/10;l<p-1;l++){int he=0;int ll=l;while(ll>0){he+=ll%10;ll=ll/10;}ll=l;if(he==sheng){string s3=s;//cout<<n1<<" "<<l<<s<<endl;while(ll>0){char c=ll%10+'0';s3=c+s3;ll=ll/10;//cout<<ll<<" "<<c<<endl;}//cout<<s3<<endl;da[flag].A=s3;da[flag].n=n1;flag++;}}}n1++;}if(flag==0){cout<<"No Solution"<<endl;}else{sort(da+0,da+flag,cmp);for(int o=0;o<flag;o++){cout<<da[o].n<<" "<<da[o].A<<endl;}}}return 0;
}

超时12分

 

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b){if(b>a){int t=a;a=b;b=t;}if(b!=0){gcd(b,a%b);	}else{return a;}
}
int issu(int a){int b=2;for(b;b<=sqrt(a);b++){if(a%b==0){return 0;}}return 1;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cout<<"Case "<<i<<endl;int k,m;cin>>k>>m;if(m/k>9||k>=10||k<=3){cout<<"No Solution"<<endl;continue;}long long int p=1;for(long long int l=0;l<k;l++){p*=10;}int n1=0,n2=0;int flag=0;long long int s1,s2;for(long long int l=p/10;l<p;l++){n1=0;n2=0;s1=l;s2=l+1;while(s1>0){n1+=s1%10;s1/=10;}//cout<<n1<<endl;if(n1!=m){continue;}while(s2>0){n2+=s2%10;s2/=10;}int pp=gcd(n1,n2);if(pp>2&&issu(pp)){flag=1;cout<<n2<<" "<<l<<endl;}}if(flag==0){cout<<"No Solution"<<endl;}}return 0;
}