# Digit-Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 855    Accepted Submission(s): 261

Problem Description
Let  S(N) be digit-sum of  N, i.e  S(109)=10,S(6)=6.

If two positive integers  a,b are given, find the least positive integer  n satisfying the condition  a×S(n)=b×S(2n).

If there is no such number then output 0.

Input
The first line contains the number of test caces  T(T10).
The next  T lines contain two positive integers  a,b(0<a,b<101).

Output
Output the answer in a new line for each test case.

Sample Input

3 2 1 4 1 3 4

Sample Output

1 0 55899

Source

a*S(n) = b * S(2n)

①:S(n) : S(2n) = b : a

②: L 为 n 中 每一位 在 [5-9] 的 内的个数

③: S(2*n) = S(n) *2 - L*9   (  减去 多出来 要进位的 )

④:  a * S(n) = b * ( S(n) * 2 - L * 9 )

⑤:  a * S(n)  = 2*b * S(n) - L*b * 9

⑥:  ( 2*b - a ) * S(n)  = L*b * 9

⑦:  ( 2*b - a) : b * 9 = S(n) : L

然后就可以根据尾数 进行贪心搜索

#include <bits/stdc++.h>
#include <iostream>
typedef long long ll;

const int MAXN = 1e5 +20;

using namespace std;

/*
g = gcd(a,b)
a = a/g, b = b/g
a * Sn = b * S2n
Sn : S2n = b : a
L = [5-9]
S2n = Sn * 2 - L*9
a*Sn = b * (Sn * 2 - L*9)
a*Sn = 2b*Sn - Lb*9
(2b - a ) * Sn   = Lb*9
(2b - a) : b*9 = Sn : L
*/
int main()
{
int T;
cin>>T;
while(T--)
{
int a,b;
cin>>a>>b;
int ans[1005];
memset(ans,0,sizeof(ans));
a = 2*b -a;
b = b*9;
int g = __gcd(a,b);
if( a == 0 )
{
cout<<1<<endl;
continue;
}
else if( 5*a > b || a < 0)
{
cout<<0<<endl;
continue;
}
else
{
a = a/g;
b = b/g;
b -= 5*a;
int k = 0;
for(int i = 0 ; i < a ;i++)
{
}
while(b)
{
int temp = min(4,b);
ans[k++] = temp;
b -= temp;
}
for(int i = k -1 ; i >= 0 ;i--)
cout<<ans[i];
cout<<endl;
}
}
return 0;
}

1