蒟蒻求助 80pts WA on #3 #10
查看原帖
蒟蒻求助 80pts WA on #3 #10
1126325
Indestructible楼主2024/7/13 13:23

代码可读性较强有注释,思路:

因为 ap−2≡a−1( mod p)a^{p-2}\equiv a^{-1}(\bmod p),所以 ap−2bx≡1( mod p)a^{p-2}bx\equiv1(\bmod p),只需计算出 ap−2ba^{p-2}b 模 pp 的逆元 (ap−2b)p−2(p=19260817)(a^{p-2}b)^{p-2}(p=19260817),使用费马小定理即可。读入取模后使用 22 次快速幂即可。

#include <bits/stdc++.h>
#define int long long // 使用 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 输出不一样,蒟蒻求助

2024/7/13 13:23
加载中...