1104 天长地久 (20 分)

题目

题目链接

题解

第一种做法：

需要一定的数学思维+枚举。

规定 S u m ( A ) Sum(A) Sum(A) 表示 A A A 的各位之和。

最重要的一点是要想到任意两个相邻自然数的最大公因子只能是1，也就是说如果 S u m ( A + 1 ) − S u m ( A ) = 1 Sum(A+1) - Sum(A) = 1 Sum(A+1)−Sum(A)=1，那么 S u m ( A + 1 ) Sum(A+1) Sum(A+1) 和 S u m ( A ) Sum(A) Sum(A) 的最大公因子只能是1，因此我们必须要让 S u m ( A + 1 ) Sum(A+1) Sum(A+1) 和 S u m ( A ) Sum(A) Sum(A) 不是相邻的自然数。进位可以让一个数的结尾从9变为0，这样就可以让 S u m ( A + 1 ) Sum(A+1) Sum(A+1) 和 S u m ( A ) Sum(A) Sum(A) 不是相邻的自然数了。

A A A可以以一个9结尾，也可以以多个9结尾。

如果以一个9结尾，那么m = n + 8，由辗转相除算法可知 gcd (n+8, n) = gcd (n, 8)，8 的因子有1、2、4、8，都不是满足条件的因子，所以公因子更不可能满足，这样，以一个9结尾的 A A A不存在。

以两个9结尾，m = n + 17，还是辗转相除法，gcd (n, 17)，最大公因子完全可以取17，且满足题目要求，所以存在满足要求的可能。

以三个9结尾，m = n + 26，gcd (n, 26)，最大公因子可以取13，所以存在满足要求的可能。

……

最终可以确定只有以一个9结尾的 A A A不存在，所以我们从k位且以99结尾的数开始枚举，枚举到k+1位的最小数字，判断枚举的每个数是否满足各位之和为m，加一后各位之和为n，且m、n的最大公因子满足题意。

按要求排序后输出。

第二种做法：

可能没想到至少以两个9结尾去枚举（就是我），但是可以不枚举全部的数，而是枚举结尾9的个数，也就是以多少个9结尾。

假设枚举到以j个9结尾，那么相当于已经确定了 A A A至少有j个9了， S u m ( A ) = j ∗ 9 + r e s t Sum(A) = j*9 + rest Sum(A)=j∗9+rest。

因为我们枚举了 A A A结尾9的个数，所以也就可以知道 S u m ( A + 1 ) Sum(A+1) Sum(A+1)的大小了（以一个9结尾 S u m ( A + 1 ) − S u m ( A ) = 8 Sum(A+1) - Sum(A) = 8 Sum(A+1)−Sum(A)=8、以两个9结尾 S u m ( A + 1 ) − S u m ( A ) = 17 Sum(A+1) - Sum(A) = 17 Sum(A+1)−Sum(A)=17、以三个9结尾 S u m ( A + 1 ) − S u m ( A ) = 26 Sum(A+1) - Sum(A) = 26 Sum(A+1)−Sum(A)=26……），先判断 S u m ( A + 1 ) = n Sum(A+1)=n Sum(A+1)=n与 m m m的最大公因子，对于满足的情况，我们去深搜 A A A的剩下的k-j位的数，这k-j的和是 r e s t rest rest。

深搜的时候需要注意：

1. 如果搜到 A A A的最高位了，那么不能为0；
2. 如果采用的vector记录结果，而不是set，还得保证第j个结尾的9（从低位向高位数）的高一位必须不能是9，因为咱们枚举的结尾的9，如果再多个9就成j+1要深搜的情况了，会出现重复。更方便的做法是用set。

最后排序输出。（如果是set不用排序，自动排序）

代码

枚举：

#include
using namespace std;
typedef long long LL;
const LL N = 1e10+10;

int vis[1100], cnt, prime[1100];

vector  ans;

bool isprime (int x) { // 大于2的素数返回true 
	if (x  T;
	for (int i = 1;i > k >> m;
		LL r = LL(pow(10,k)); // k+1位最小数，即1后面接k个0 
		LL l = r/100LL + 99LL; // k位且以99结尾的最小数 
		for (LL j = l;j