题解 | #小乐乐与二段数#

#include <stdio.h>

int a[9999],b[999];
int m,total,s,t,aptotal,apm,aps,apt,k;//我们让total来存储这个数的位数 这样n就可以用total-m来赋值
int n; //注意这里的n是我们要输入的值

//由于使用到了全局变量，所以这里不用传递函数参量
//这部分内容主要是还原二段数，判断其是否满足大于输入数字（如：2019）

int ck()
{
	int p,r;
	//我们让p储存s，r存储t
	if (total > 5)
		return 1;
	p=s;
	r=t;
	for(int q=0;q<m;q++)
	{
		p=p*10+s;
	}
	//我们需要将p扩10的total-m次方
	for (int q = 0; q < total-m; q++)
		p = p * 10;
	for (int q = 1; q < total-m; q++)
		r = r * 10 + t;
	return p+r>n;
}

int main()
{
	while(scanf("%d",&n),n)
	{
		printf("%d: ", n);
		if (n == 1) {
			puts("10");
			continue;
		}
		//下面的数组可以参见上述理解
		a[0]=1;
		b[0]=1;
		for(int i=1;i<9999;i++)
			a[i]=(a[i-1]*10+1)%n;
		for (int i = 1; i < 999; i++)
			b[i] = b[i - 1] * 10 % n;
		
		
		//这部分内容便是举例情况，并对每种情况进行判断，考虑到是从小到大的枚举顺序，因而只要满足以下三个条件，那么break了！
		for (total = 1, aps = 0; total < 9999; total++) {
			k = 0;
			//这一部分便是 所说的对特殊数字 如：10、25、50等的快速判断
			if ((n % 10 == 0 || n % 25 == 0) && total> 11)
				k = total - 11;
			for (m = k; m < total; m++)
				for (s = 1; s < 10; s++)
					for (t = 0; t < (n % 10 ? 10 : 1); t++)
						//这里的三个判断条件很有必要说一下
						//1.二段数两端数字 即s、t 不一样 t != s
						//2.还原后的二段式必须是n的整数倍，详解见上述
						//3.ck()，还原的数字必须比输入的数字要大 不能为其本身
						if(t!=s&&(((long long)a[m]) * b[total - m] * s + a[total - m - 1] * t) % n == 0 && ck()&&
							(!aps||s<aps))
						{
							aptotal=total;
							apm=m;
							aps=s;
							apt=t;
						}
			if (aps)
				break;
		}
		for (int x = 0; x < apm + 1; x++)
			printf("%d", aps);
		for (int x = 0; x < aptotal - apm; x++)
			printf("%d", apt);
		printf("\n");
	}
}