代码可读性较强有注释,思路:
因为 ap−2≡a−1(modp),所以 ap−2bx≡1(modp),只需计算出 ap−2b 模 p 的逆元 (ap−2b)p−2(p=19260817),使用费马小定理即可。读入取模后使用 2 次快速幂即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 19260817;
int a, b;
int read(int& x)
{
x = 0;
char s = getchar();
while (s <= '0' || s >= '9')
{
s = getchar();
}
while (s >= '0' && s <= '9')
{
x = (x * 10 + s - '0') % mod;
s = getchar();
}
}
int fast_pow(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
signed main()
{
read(a), read(b);
if (!b)
{
printf("Angry!\n");
return 0;
}
int inverse_a = fast_pow(a, mod - 2);
int ans = fast_pow(inverse_a * b % mod, mod - 2);
printf("%lld\n", ans);
return 0;
}
同样的代码,C++ 20 O2 是这样的,C++ 14 (GCC 9) 是这样的,而且本地和洛谷 IDE 输出不一样,蒟蒻求助