自动搬运

查看原文

来自洛谷，原作者为

	Tomwsc 长风破浪会有时，直挂云帆济沧海

搬运于2025-08-24 23:13:46，当前版本为作者最后更新于2025-04-18 19:12:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12217 [蓝桥杯 2023 国 Java B] 逆元 题解

思路

两种不同的做法，由于我比较蒟，所以介绍暴力做法。

容易由费马小定理得：$a^{m-2}\bmod m$ 即为 $a \bmod m$ 的逆元。这可以使用快速幂实现，所以直接暴力跑即可。时间很短，只需要两分钟……

代码

#include<bits/stdc++.h>
#define int long long
#define inf (1ll << 62)
#define regint register int
#define pb push_back
#define mp make_pair
#define PII pair<int , int>
using namespace std;
const int mod = 2146516019;
int ans;

inline int ksm(int base , int x , int mod) {
	int result = 1;
	while(x) {
		if(x & 1)
			result = (result * base) % mod;
		x >>= 1;
		base = (base * base) % mod;
	}
	return result;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(regint i = 1;i <= 233333333;i ++)
		ans ^= ksm(i , mod - 2 , mod);
	cout << ans;
	return 0;
}