(相关资料图)

除法取模运算（公式法）

注意，除法是指算术除法后向下取整，即计算机中的整数除法如果遇到(a/b)%m的问题，直接运算a/b然后取模是错误的，这时，我们往往需要求出b的逆元，然后将式子改为：(a*b的逆元)%m的形式，此时先做乘法再取模就正确了。

除此之外，还有一种方法，就是用以下公式求解：

x/d%m=x%(d*m)/d

证明:

\[\begin{aligned}\frac{x}{d} \%m &= \frac{x}{d}-m\cdot \frac{x}{d\cdot m}\\\frac{x\%(d\cdot m)}{d}&=\frac{x-d\cdot m\cdot \frac{x}{d\cdot m}}{d}\\&=\frac{x}{d}-m\cdot \frac{x}{d\cdot m}\end{aligned}\]例题

[原题链接](Problem - I - Codeforces)

题目大意

给两个整数n，m。求\(\frac{1}{n}\) 小数点后第m位。\(1\leq n \leq 10^5,1\leq m \leq 10^9\)

样例1输入

3 5

输出

3

样例2输入

233 23

输出

5

思路

设\(k=\frac{1}{n}\)，则求k小数点后第1位，就是把k乘以10然后取个位，求k小数点后第2位，就是k乘以100然后取个位，以此类推

故求k小数点后第m位就是\(\frac{10^m}{n} \% 10\)，然后用公式转化为：\(\frac{10^m \%(10\cdot n)}{n}\)。然后就可以使用快速幂计算。

AC代码

#includeusing namespace std;using i64 = long long;i64 n, m;i64 qp(i64 a, i64 b) {i64 res = 1;while (b) {if (b & 1) {res = res * a % (10 * n);b--;}a = a * a % (10 * n);b /= 2;}return res;}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;cout << qp(10, m) / n;return 0;}