If two positive integers a,ba,b are given, find the least positive integer nn satisfying the condition a×S(n)=b×S(2n)a×S(n)=b×S(2n).
If there is no such number then output 0.
InputThe first line contains the number of test caces T(T≤10)T(T≤10).
The next TT lines contain two positive integers a,b(0<a,b<101)a,b(0<a,b<101).
OutputOutput the answer in a new line for each test case.
Sample Input
3
2 1
4 1
3 4
Sample Output
1
0
55899
题意：S(n)表示的是求数字n十进制下每个数位的数字的和。给你两个常数a，b，让你找到最小的值 n，使得a * S(n) == b * S(2 * n)。
考察S(n)与S(2n)的关系，可以得到，对于组成n的每一位数x，其对S(n)的贡献为x，对S(2n)的贡献 为2x(x < 4)或2x - 9(x >= 5)。 因此，假设 n 中含有大于等于5的数字L个。S(2n) = 2 * S(n) - 9 * L成立。结合题目要求的等式 a * S(n)=b * S(2n)，则： a * S(n) = b * (2 * S(n) - 9 * L) ⟺a * S(n) = 2b * S(n) - 9 * b * L ⟺(2b - a) * S(n) = 9 * b * L ⟺S(n) / L = 9 * b / 2b - a 由于S(n), L, 9 * b, 2b - a均为整数，故 S(n) = k * (9 * b) ，L = k * (2b - a)。同时，由于要求 n 最小， 可知 k 取 1 时最小。 因此，首先构造长为L，每个字符均为5（由于L个数字必须大于等于5）的字符串，同时S(n) -= 5 * L。对于多余的S(n)，为使得n尽可能小（即串长最小，大的数字尽可能向个位数靠拢），故优先将串尾 的字符增长到9。 若长为L的字符串已经全部为9。此时不得不增加串长，则优先在串首增加4（不在L个数字中的均小于 等于4），直到S(n)全部用尽。 需要注意，当a > 2 * b以及5 * a < b时，不可构造，输出0。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
int ans[]; int gcd(int a,int b){
return b==?a:gcd(b,a%b);
}
int main(){
int t;
cin>>t;
for(int i=;i<=t;i++){
int a,b;
cin>>a>>b;
int n=*b,m=*b-a;
if(a==*b){
cout<<""<<endl;
continue;
}
if(a>*b||n<*m){
cout<<""<<endl;
continue;
}
int k=gcd(m,n);
m/=k,n/=k;
n-=*m;
for(int i=;i<m;i++,n-=k){
k=min(,n);
ans[i]=+k;
}
m--;
while(n>){
ans[++m]=;
n-=;
}
if(n) ans[++m]=n;
for(int j=m;j>=;j--){
cout<<ans[j];
}
cout<<endl;
}
return ;
}