3657103_ac_16ms_176k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 50 行

#include <stdio.h>

__int64 mod;

__int64 power(__int64 a, __int64 p)
{
	if (p == 1)
	{
		return a % mod;
	}
	if (p % 2 == 0)
	{
		return power(a * a % mod, p / 2) % mod;
	}
	else
	{
		return a * power(a, p - 1) % mod;
	}
}

bool prime(int a)
{
	if (a % 2 == 0)
		return false;
	for (int i = 3; i * i <= a; i += 2)
	{
		if (a % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main()
{
	__int64 a, p;

	while (scanf("%I64d%I64d", &p, &a) == 2 && p && a)
	{
		if (prime((int)p))
		{
			puts("no");
			continue;
		}
		mod = p;
		puts(power(a, p) == a ? "yes" : "no");
	}
	return 0;
}