题解 CF1409D 【Decrease the Sum of Digits】
江户川·萝卜
2020-09-05 12:14:23
### 题意：
给定n,求一个最小的x，使$n+x$的各位数之和小于等于s。
### 解法
加着加着各位数之和变小了，我们就想到了进位。
我们就可以：从低位一位一位往高位进位，直到满足条件为止。
原因:
- 低位进位需要的代价远比高位进位需要的代价小。
- 假设本来高位加一次需要 $10^k$ ，如果从低位往上进位的话，就用了 $<10^k$ 的代价，而且还让各位数之和更少。
应该是很好理解的。
代码：
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long n,ans,r;
int t,s,tot;
int main(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%lld%d",&n,&s);
tot=ans=0;
r=n;
while(r){
tot+=r%10;
r/=10;
}//求出n的各位数之和
if(tot<=s){
printf("0\n");
continue;
}//一开始n的各位数之和就小于等于s
for(unsigned long long res=1;tot>s&&res<n;res*=10){
int c=n/res%10;
if(c==0) continue;
ans+=(10-c)*res;
n+=(10-c)*res;
tot=0;
r=n;
while(r){
tot+=r%10;
r/=10;
}//求各位数之和
}//模拟从低位往高位进位
printf("%lld\n",ans);
}
return 0;
}
```