题目简述
给定两个数 \(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!}
\]
标签:lfloor,10,right,arc111,题解,bmod,long,ans
From: https://www.cnblogs.com/So-noSlack/p/17736361.html