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;
} 
京公网安备 11010502036488号