Digit-Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 782 Accepted Submission(s):
241
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.
If two positive integers a,b
If there is no such number then output 0.
Input
The first line contains the number of test caces T(T≤10)
.
The next T
lines contain two positive integers a,b(0<a,b<101)
.
The next T
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
Recommend
liuyiding
![](https://images2018.cnblogs.com/blog/1322499/201805/1322499-20180514001338159-1492984827.png)
#include<stdio.h> #include<string.h> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #include<string.h> #include<algorithm> #include<vector> #include<stdio.h> #include<cstdio> #include<time.h> #include<stack> #include<queue> #include<deque> #include<map> #define inf 0x3f3f3f3f #define ll long long using namespace std; int d[100005]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d %d",&a,&b); bool ff=0; bool f=0; int x=2*b-a; int y=9*b; if(x==0) { cout<<1<<endl; continue; } else if(x<0||5*x>y) { cout<<"0"<<endl; continue; } int xx,yy; xx=max(x,y); yy=min(x,y); int pp=gcd(xx,yy); x=x/pp; y=y/pp; y=y-5*x; memset(d,0,sizeof(d)); for(int i=1;i<=x;i++) d[i]=5; int i=1; while(y>=4) { y=y-4; d[i]+=4; i++; } x=max(x,i-1); if(y) { d[i]+=y; if(x==i-1) x++; } for(int j=x;j>=1;j--) cout<<d[j]; cout<<endl; } return 0; }