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

· · 题解

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;
}