出题人题解 | #Tachibana Kanade Loves Probability#

原题解链接：https://ac.nowcoder.com/discuss/173818

简单的模拟题。

题目等价于求分数 $\frac{a}{b}\backslash frac\{a\}\{b\}$ 的小数点后$K_{1}K\_1$ 到$K_{2}K\_2$ 位的所有数字。

直接暴力模拟除法过程是肯定会 $TT$的，但是我们发现我们不用从头开始模拟，只需要从$K_{1}K\_1$ ​ 位开始模拟就可以了。

直接通过快速幂+取模算出第 $K_{1}K\_1$ ​ 位的数字。然后我们发现$K_2-K_1\le 10^{5}K\_2-K\_1\; \backslash leq\; 10^5$ ，所以暴力枚举除法过程就可以。

时间复杂度 $O(n)O(n)$。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline LL qpow(LL a,LL b,LL p){
	LL res = 1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1) res = res * a % p;
	return res;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        LL a,b,k1,k2;
        std::cin >> a >> b >> k1 >> k2;
        LL ans = ((a % b) % b * qpow(10, k1 - 1, b)) % b;
        for(LL i = k1;i <= k2;i++,ans = ans % b) {
            ans *= 10;
            std::cout << ans / b;
        }
        std::cout << std::endl;
    }
	return 0;
}