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

题目链接：https://ac.nowcoder.com/acm/contest/548/B

题意：计算m/n小数点后k1位到k2位，$\mathrm{1\le m\le n\le 109，1<=k1<=k2<=109,0<=k2-k1<=105,T<=20。}$

$\mathrm{思路：计算小数可以模拟除法一位一位地算，但需要把k1之前的计算出来，不然没法计算k1到k2的，看到数据范围1<=k1<=k2<=109,0<=k2-k1<=105，全部模拟的话肯定会超时，k1之前的是不能直接算，计算结果在n/m中，不访将m乘10k1-1，再对n取模，这里需要用快速幂，此时再模拟除法计算k2-k1+1次就可以了。另外需要用long\; long，不然会wa。}$

$\mathrm{AC代码：}$

#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("\n");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("\n");}return 0;
}