题解：P9006 [入门赛 #9] 神树大人挥动魔杖 (Hard Version)

Farewell_Bood · 2024-09-21 23:02:44 · 题解

太好了，又找到了一个可以练习差分的题目了。

我们假设有 x 个小精灵，则每一组的个数至少为 a/k 个。那么剩余的 x \bmod k 个分别分到了 1 至 x \bmod k 组中（不从 0 开始）。

我们要先求出 a \bmod k 的值，为什么呢？因为它善无法直接做取模的下取整除法。

#include<bits/stdc++.h>
using namespace std;
const long long mod=100000007;
long long ans[1000001];
long long qpow(long long di,long long zhi,long long Mod){
    long long ans=1;
    while(zhi){
        if(zhi&1) ans=ans*di%Mod;
        di=di*di%Mod;
        zhi>>=1;
    }
    return ans%Mod;
}
long long n,k,cnt=1;
int main(){
    cin>>n>>k;
    long long x=(qpow(10,n-1,k)-1+k)%k;
    long long y=(qpow(10,n-1,mod)-1-x+mod)*qpow(k,mod-2,mod)%mod;
    for(int i=0;i<k;i++){
        ans[i]-=y;
        if(i!=0&&i<=x) ans[i]--;
    }
    x=(qpow(10,n,k)-1+k)%k;
    y=(qpow(10,n,mod)-1-x+mod)*qpow(k,mod-2,mod)%mod;
    for(int i=0;i<k;i++){
        ans[i]+=y;
        if(i!=0&&i<=x) ans[i]++;
        ans[i]=(ans[i]+mod)%mod;
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

所以这道题就这么水灵灵的过啦！