2019年9月 PAT甲级 7-1 Forever 题解

2019年9月 PAT甲级 7-1 Forever 题解

题意

输入N对K和m，要求找到所有K位数满足：
1.该数的和为m；
2.该数+1的和为n；
3.m和n的最大公约数是一个大于2的质数；

思路

K<10，最大为9，暴力枚举是10的9次，肯定超时，需要缩小枚举范围。

看到这题，我觉得一种数学直觉是大家都会有的，那就是：任意一个数p和p+1一般都是互质的吧。事实也是如此（我一时没想到反例）。

这就意味着，要是一个数简单+1，若没有进位，那么肯定无法符合要求，因为这样n和m也只相差一，它们是互质的（最大公约数为1，不是大于2的质数）。于是，我们就知道了，我们要枚举的是有进位的那些数。也就是尾数为9、99、999、9999……的那些数。而且，更有趣的是，我们可以根据尾数情况直接得到n和m的差值！举个例子9+1=10，位数和从9到1，m-n=8；99+1=100，位数和从18到100，m-n=17。（代码里的yes函数就在判断这个）

考虑到位数和的范围是其实很小，是1-90，也就是说m和n都是1-90；那我们就可以直接去算1-90这些数，哪些组合是符合条件3的？可以直接打表看。这就是我下面init函数里做的事儿。处理结果mn[i][j]为true表明（i,j）是符合要求的（m,n）对。事实上，根据m、n的差值和mn数组，可以进一步缩小可能的数位和，m和n的差因为是进位造成的，所以是有限制的，只能是17、26、35、44这些数（可以通过我注释掉的代码验证）。也就是说，我们只需要枚举以99、999、9999、99999为位数的数即可。

那剩下来的任务就是枚举了。为了控制好不同位数9尾数的进位，我们需要对前面剩余x个数位从10的x-1次方（形式为10…0）枚举到10的x次方减2（形式为99…98）。枚举代码在main函数里，草稿纸上写写对应一下下标就出来了。枚举并根据mn数组判断，最后把答案加到set里并输出。

至此，本场考试最难的一道题成功AC！（我没看AC率，做到后面才知道这道题过的人最少）代码如下：

#include <iostream>
#include <string>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;

bool mn[100][100];//[i][j]表示(i,j)是符合要求的数对。 

int gcd(int a,int b){//辗转相除法求最大公约数 
	if(b==0)return 2;
	return a%b==0?b:gcd(b,a%b);
}

bool isPrime(int n){//判断n是否为质数 
	for(int i=2;i<n;i++){
		if(gcd(n,i)!=1)return false;
	}	
	return true;
} 

void init(){//预先达标符合要求的m、n对 
	for(int i=2;i<=90;i++){
		for(int j=2;j<=90;j++){
			int GCD=gcd(i,j);
			if(GCD>2&&isPrime(GCD)){
//				cout<<"("<<i<<","<<j<<")"<<endl;
				mn[i][j]=true;
			}
		}
	}
}

int sum(int n){//求数位和 
	int ret=0;
	do{
		ret+=n%10;
		n/=10;
	}while(n);
	return ret;
}

int POW(int n){//返回10的n次方 
	int ret=1;
	while(n--)ret*=10;
	return ret;
}

//bool yes(int n){
//	return n==8||n==17||n==26||n==35||n==44||n==53||n==62||n==71||n==80;
//}

int main(){
	int N,K,m;
	cin>>N;
	init();
	
//	for(int i=1;i<=90;i++){//好奇的人可以看一下 
//		for(int j=1;j<=90;j++){
//			if(yes(i-j)&&mn[i][j])cout<<"("<<i<<","<<j<<")"<<i-j<<endl;
//		}
//	}

	for(int Case=1;Case<=N;Case++){
		cin>>K>>m;
		set<pair<int,int> >ans;
		cout<<"Case "<<Case<<endl;
		for(int i=2;i<=min(5,K-1);i++){
			for(int j=POW(K-i-1);j<=POW(K-i)-2;j++){
				int num=j*POW(i)+POW(i)-1;
				if(num>=POW(K-1)&&num<POW(K)-1&&sum(num)==m){
					int sumi=sum(num),sumip1=sum(num+1);
					if(mn[sumi][sumip1]){
						ans.insert(make_pair(sumi,num));
					}
				}
			}
		}
		if(ans.size()==0){
			cout<<"No Solution"<<endl;
			continue;
		}
		for(set<pair<int,int> >::iterator it=ans.begin();it!=ans.end();it++){
			cout<<it->first<<" "<<it->second<<endl;
		}
	}
	return 0;
} 

/*
输入N对K和m，要求找到所有K位数满足：
1.该数的和为m；
2.该数+1的和为n；
3.m和n的最大公约数是一个大于2的质数； 
*/