CodeForces - 1409 - Decrease the Sum of Digits - 【贪心+数学】题解-蒲公英云

CodeForces - 1409 - Decrease the Sum of Digits - 【贪心+数学】题解

1.题目

You are given a positive integer n. In one move, you can increase n by one (i.e. make n:=n+1). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of n be less than or equal to s.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.

The only line of the test case contains two integers n and s (1≤n≤1018; 1≤s≤162).

Output
For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of n be less than or equal to s.

Example
Input
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1
Output
8
0
500
2128012501878
899999999999999999

2.思路

思路：sum(n)表示n的位数之和
题意：给你两个数n和s,可以进行n++操作,使得n的位数之和sum(n)<=s,所需要对n进行的最小操作步数.
我们发现想要让sum(n)<=s,n++肯定会使n的位数之和变大,比如n=3452,s=10,n++变为3453，3454, 3455，，，，3459,只有当n变为离它最近的能被10整除的数时,即3460时,sum(n)才会减少。
因此我们发现了一个规律:n变为m使得sum(m)<=s,m一定是可以被10整除的(观察测试样例也可以发现)

3.AC代码

#include<iostream>
#define ull unsigned long long 
using namespace std;
ull f( ull n) //求出位数和 
{ 
   ull sum=0;
   while(n)
   { 
      sum+=n%10;
      n/=10;    
   }    
   return sum;
} 
int  main()
{ 
   int T;
   cin>>T;
   while(T--)
   { 
         ull n,s;
         cin>>n>>s;
         ull ans=0,now=1;  //now是 每次n++,执行的操作步数 
         while(f(n)>s)
         { 
         if(n%10==0)  n/=10,now*=10; //当n能被10整除时,其末尾为0,对位数之和无影响,我们去除最后一位 
         else   ++n,ans+=now;        //对应的下次进行n++时,执行的操作步数就要乘10 
      }
      cout<<ans<<"\n";
   }
   return 0;    
}