题目简述
给定两个数 \(n\) 和 \(m\)，输出 \(\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m\) 的值。
数据范围：\(n \le 10^{18},m \le 10^4\)
思路
首先看到数据范围还是很大的，直接快速幂会炸，所以需要一些优化操作。
推理如下：
\[\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m \equiv \left\lfloor\frac{10^n}{m}\right\rfloor - k \times m \bmod m \equiv \left\lfloor\frac{10^n - k \times m^2}{m}\right\rfloor \bmod m \equiv \left\lfloor\frac{10^n \bmod m^2}{m}\right\rfloor \bmod m
\]
经过以上推理，可以发现，仅需用快速幂求 \(10^n \bmod m^2\) 的值即可，时间复杂度 \(O(\log n)\)，可以通过。
其中快速幂的代码可以用循环实现（本人觉得比较好用）。
long long qpow(long long a, long long b, long long p) {
long long ans = 1;
while(b) {
if(b & 1) ans *= (a % p), ans %= p;
a = (a * a % p);
b /= 2;
}
return ans;
}
解决快速幂后，此题就非常简单了，代码如下：
#include<iostream>
using namespace std;
long long n, m, ans = 0;
long long qpow(long long a, long long b, long long p) {
ans = 1;
while(b) {
if(b & 1) ans *= (a % p), ans %= p;
a = (a * a % p);
b /= 2;
}
return ans;
}
int main() {
cin >> n >> m;
cout << qpow(10, n, m * m) / m << endl;
return 0;
}
\[\texttt{The end!}
\]