题目传送门
题目大意：
定义S(N) 为数字N每个位上数字的和。再给两个数a,b，求最小的正整数n，使得 a×S(n)=b×S(2n)
思路在代码中会详细解说，请看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int ans[100];
int tot;
int gcd(int n,int m)
{
return m==0?n:gcd(m,n%m);
}
int main()
{
int T;scanf("%d",&T);while(T--){
tot=0;int a,b;scanf("%d%d",&a,&b);/*题目要求是否存在 a*s(k)=b*s(2*k)的最小 k s(k)代表k的每个数的和，比如 s(152)=1+5+2=8; 怎样弄呢？首先，我们知道 s(k)*2 和 s(2*k) 并不一定相等 它们有什么关系没？我们知道当 k 的每个数都是<5 那么 2*k 的每个数都是 k 每个数的两倍，因为没有进位所以有 s(k)*2=s(2*k)那么当 k 存在 >=5 的数呢？ 首先 <5 的数是不是关系已经确 定我们再来确定 >=5 的数的关系，假如只有一个数组成的数 a >=5,有s(a)=a那么 s(2*a)=1+(2*a)%10=1+2*a-10=2*a-9（10<=2*a<=18,所以是-10）一个数 >=5 当然也可以等价于多个数 >=5的情况 ，所以设 >=5的个数为 len有：a*s(k)=b*s(2*k)=b*(s(k)*2-9*len)=>len/s(k)=(2*b-a)/9*b 再看下面代码 */int m=2*b-a;int n=9*b;if(m<0||5*m>n){
printf("0\n");continue;}/*m=2*b-a，相当于 len 1.m<0, s(k)即n=9*b是一定>0 ，但是>=5的数的个数不可能是负数所以此情况不存在 2.m相当于 k 中 >=5的数的个数,n相当于 k 的 每个数的和，所以s(k)的min值是 5*m+((组成k的数的个数)-m )*1是不是有 5*m<=n 所以 5*m>n 就代表不存在了 */ if(m==0){
printf("1\n");continue;}/*排除 k 不存在的情况，并且 k 中没有 >=5的数，你说最小的 k 是不是1？ 因为m==0,s(k)可以是随便一个值，都可以满足 len/s(k)=(2*b-a)/9*b 当然选择最小的，当然是1,因为0代表不存在啊 */ int g=gcd(n,m);m/=g;n/=g;n-=m*5;/*为什么有这个操作？因为要求最小的k，举个例子k=55555, 有s(55555)=25,len=5,所以 len/s(k)=5/25=m/n;所以5*b=25*a,所以b=5*a， 所以 a*s(55555)=b*s(111110)=5*a*s(111110)但是操作 m/=g n/=g 后 len/5=1 s(55555)/5=5 ,就是k=5 所以 a*s(5)=b*s(10) 难道不可以？如果还不理解，就多写几个例子 */int M;for(int i=1;i<=m;i++){
M=min(4,n);n-=M;ans[tot++]=5+M;}/*这个操作有什么用？就是把上面的例子 k=55555 变成 k=5的过程 作用其实比较好懂，看例子 k=88888111 s(k)=43, len=5,s(k)-len*5=18;操作后k=99997,下面的操作会 逆向输出 79999 难道s(99997) 和 s(79999) 不一样吗？所以你应该懂了吧？就是把后面的len个数尽量变成最大值9,数的个数就会有可能变少，前面的数也有可能会变小这样是不是会得到最小值？ 当然！！ */ while(n>0){
M=min(4,n);n-=M;ans[tot++]=M;}/*后面的len个数都是9了，但是s(k)还>0,所以前面<5的数也要弄，所以从后往前填 <5的数 */ for(int i=tot-1;i>=0;i--){
printf("%d",ans[i]);} //再逆向输出 printf("\n");}return 0;
}