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

阳光穿透心脏的1/2处 2021-07-24 22:44 374阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.思路
         *  3.AC代码

### 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;	
    }