牛客BC120 小乐乐与二段数的一些思考与补充
题目
二段数为仅包含两种十进制数字的s和t，且s不为0，s所有均出现在所有t的前面。举个例子：4444444111是二段数，51、10000000000和5555555556666也是，这是小乐乐被老师问道：给任意一个正整数n，求出比n大且是n倍数的最小二段数？
提示：以下是本篇文章正文内容，下面案例可供参考
一、题意分析
这道题理解起来还是有一定难度的，看一眼往往很懵！不过分开来理解其实并不难，这样来看，首先二段数是一个特定设置的长串数字，例如：ssssssssstttttt（9个s和6个t，我们可以这样还原该长串数字，即：111111111*10^6*s+111111*t，这样看，是不是清楚很多！ 上面是第一个难点，第二个难点便是n的倍数问题，有的数字过于冗长，按照原始的计算方法不能及时有效的获取结果，例如：要寻找2019的n的倍数，通过计算可以得到既是2019的倍数又是二段数的结果为9999999993（9个9，1个3），这要计算下来需要浪费多少内存啊！所以，我将在下面的内容中着重说明，这个问题，并对网上所找到的代码简单说一下自己的一些理解。
二、代码及解读
1.数字过大，除余有妙招
先来看一下下面这段数学推算，这里假定输入的数字为2019：
1%2019=1；
11%2019=11；
111%2019=111；
1111%2019=1111；
——————————
现在看好了!
11111%2019=(1111*10+1)%2019=(1111%2019*10)%2019;
同理：
111111%2019=（11111%2019*10+1）%2019
所以利用此等关系逻辑，便可以极大地缩减运算量，可以通过预先查表的方法，实现数据的快速映射，获得所需的的结果，下面我们用代码来实现这部分功能。抛开整个代码的总体轮廓，我们先对其中这部分问题的代码进行详细解读。
//根据二段数的特性，设定两个矩阵：a[9999]与b[999]
int a[9999],b[999]
int m,total,s,t,aptotal,apm,aps,apt,k;
int n;
//n为输入的数字 如上文所提到的 2019
//total为二段数的总位数
//m,total-m,s,t 分别对应 上文图中所绘制的 表达二段数所需的四个参数
//apm,aptotal-apm,aps,apt 分别对应最后判断筛选完成后的 二段数的样子
int main()
{
while(scanf("%d",&n),n)
{
printf("%d: ", n);
if (n == 1) {
puts("10");
continue;
}
//a[0] 至 a[3] 分别为 1、11、111、1111
//从a[4]起，将会利用1111的计算结果进行后续的推算
//即使a[4]并不是11111，但其代表11111%2019的结果
//同理b[i]也是这样，其必要性来自于这个公式，111111111\*10^6\*s+111111*t。
//a[i]用来对应式子中的1111...11
//b[i]则对应式中的10^6
//a[i]为（i+1）个1除以N的余数
//b[i]就是10的i次方除以N的余数。
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;
//下式为还原二段数与判断的结果
//可以看到充分利用了我们所提到的简化运算
//这里我曾疑惑了好久，那便是还原后的数字不为原数，可以进行验证
//输入的数字为2019，判断正确后，通过下式返回的数字为 135273 当然该数字为2019的整倍数，其就代表了 9999999993 % 2019，哈哈 非常有趣啊！
(((long long)a[m]) * b[total - m] * s + a[total - m - 1] * t) % n == 0
//下面的内容便是最后的输出，考虑到数组从0下标开始，所以apm需要加1
for (int x = 0; x < apm + 1; x++)
printf("%d", aps);
for (int x = 0; x < aptotal - apm; x++)
printf("%d", apt);
printf("\n");
}
}
2. 整体代码理解
这部分的内容较多，我对其理解不是特别透彻，只能就其中清晰的部分，进行解读，哪里不正确欢迎各位补充和纠正啊！
虽然，我们对运算进行了极大地简化，但考虑到输入特殊数字的情况，需要“因地制宜”，我这里不知用什么名词比较恰当，应该说对10与25成倍数的数字，予以特殊“关怀”。
空说无意，我们结合代码来看！
#include <stdio.h>
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");
}
三、总结
这里展示一下输出结果，文中的代码也是参考自网上，文中理解主要是结合网上的一些描述后自我再次理解后的想法，看到网上许多的理解并不是非常详细，在此有必要对其进行补充说明，其中不正确或需要补充的东西，欢迎大家评论留言，谢谢！
结果展示：
部分代码和理解来源于，以下网址链接：
海岛Blog nirvana · rebirth 平凡的昊