求小数点后第几位数（模拟+快速幂）

链接：https://ac.nowcoder.com/acm/contest/548/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
立华奏在学习初中数学的时候遇到了这样一道大水题：
“设箱子内有 n 个球，其中给 m 个球打上标记，设一次摸球摸到每一个球的概率均等，求一次摸球摸到打标记的球的概率”
“emmm...语言入门题”
但是她改了一下询问方式：设最终的答案为 p ,请输出 p 小数点后 K1到 K2位的所有数字（若不足则用 0 补齐）
输入描述:

第一行一个整数 T,表示有 T 组数据。
接下来每行包含四个整数 m,n,K1,K2，意义如「题目描述」所示。

输出描述:

输出 T 行，每行输出 K2−K1+1个数，表示答案。
注意同行的数字中间不需要用空格隔开。

示例1
输入
复制

5
2 3 2 3
1 7 1 7
2 5 1 3
12345 54321 3 10
12345 54321 100000 100010

输出
复制

66
1428571
400
72601756
78428232175

备注:

1≤m≤n≤10^9,1≤K1≤K2≤10^9

；
0≤K2−K1≤10^5,T≤20。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
int m,n,k1,k2;
ll ksm(ll a,ll b){
    ll s=1;
    while(b){
        if(b&1){
            a%=n;
            s%=n;
            s*=a;
        }
        a%=n;
        a*=a;
        b>>=1;
    }
    return s%n;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d",&m,&n,&k1,&k2);
        ll t=(m%n*ksm(10,k1-1))%n;
        for(int i=k1;i<=k2;i++){
            printf("%d",t*10/n);
            t*=10;
            t%=n;
        }
        printf("\n");
    }
    return 0;
}