除法取模运算（公式法）

注意，除法是指算术除法后向下取整，即计算机中的整数除法
如果遇到(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代码

#include<bits/stdc++.h>
using 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;
}