牛客网练习赛44-B（快速幂+模拟）

#include<bits/stdc++.h>
using namespace std;

int T,k1,k2;
long long m,n;

void QuickPower(){
    long long b=10;
    long long a=k1-1;
    while(a){
        if(a&1)
            m=(m*b)%n;
        a>>=1;
        b*=b;
        b%=n;
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%d%d",&m,&n,&k1,&k2);
        if(m==n){
            for(int i=0;i<=k2-k1;++i)
                printf("0");
            printf("
");
            continue;
        }
        QuickPower();
        for(int i=0;i<=k2-k1;++i){
            m*=10;
            for(int j=9;j>=0;--j){
                long long tmp=j*n;
                if(tmp<=m){
                    printf("%d",j);
                    m-=tmp;
                    break;
                }
            }
        }
        printf("
");
    }
    return 0;
}