Boj 15711) 환상의 짝꿍

문제

백준 15711

설명

A+B=S 가 주어졌을 때 S 가 두 소수의 합으로 되는지를 구하는 문제이다.

S 가 짝수라면

• S > 2 이면 그 유명한 골드바흐의 추측 을 사용할 수 있다. 컴퓨터로 몇경 이상을 돌려봤을 때 성립하기 때문에 주어진 범위 내에선 성립하게 된다.
• S == 2 이면 불가능이 자명하다

S가 홀수라면

• S-2 가 소수여야 성립한다. 왜냐하면 2 이상의 모든 소수는 홀수이므로 짝수인 소수인 2 와의 합 외에는 답이 될 수 없기 때문이다.

이때 S-2 가 소수인지를 어떻게 구할지가 문제가 된다. S < 2 * 10^12 로 굉장히 큰 수이기 때문이다.

이를 해결하는 방법은 크게 2가지를 많이 사용한다. 하나는 에라스토테네스의 체, 다른 하나는 Miller-Rarbin 의 소수테스트를 사용하는 방법이다.

에라스토테네스 체

코드

using ll = long long;
const int MAXVAL = 2000001;
bool arr[MAXVAL];
ll primes[500000], n_prime;

int main()
{
	arr[1] = true;
	for (int i = 2; i < MAXVAL; i++)
		for (int j = i + i; j < MAXVAL; j += i)
			arr[j] = true;

	for (int i = 2; i < MAXVAL; i++)
		if (!arr[i]) primes[n_prime++] = i;
	
	int T; cin >> T;
	while (T--)
	{
		ll a, b; cin >> a >> b;
		ll S = a + b;

		bool r = true;
		if (S & 0b1)
		{
			S -= 2;
			if (S >= MAXVAL)
			{
				for (int i = 0; i < n_prime; i++)
					if (S % primes[i] == 0) { r = false; break; }
			}
			else r = !arr[S];		
		}
		else r = S > 2;
	
		cout << (r ? "YES\n" : "NO\n");
	}
}

시간 복잡도

O(\(148993\))

설명

2*10^12 미만의 수 S 가 소수인지 판정을 하는 브루트포스 방법으로는 sqrt(S) 이하의 모든 소수에 대해서 나누어 떨어지는지 테스트하는 방법이 있다.

이를 위해서 sqrt(2*10^12) 이하의 모든 소수를 에라스토테네스의 체로 미리 구해놓고, 범위 내에 있으면 소수인지만 체크하고, 범위 초과시 위에서 설명한 브루트포스 방법을 사용한다.

Miller-Rarbin

코드

using ll = long long;

ll ModMul(ll a, ll b, ll MOD)
{
	// gcc x64  에서 가능
	// https://stackoverflow.com/questions/16088282/is-there-a-128-bit-integer-in-gcc
	// __int128 tmp = a;
	// return __int128(a) * b % MOD;

	ll r = 0;
	while (b)
	{
		if (b & 1) r = (r + a) % MOD;
		a = (a << 1) % MOD;
		b >>= 1;
	}
	return r;
}


ll ModPow(ll a, ll b, ll MOD)
{
	ll r = 1;
	while (b)
	{
		if (b & 1) r = ModMul(r, a, MOD);
		a = ModMul(a, a, MOD);
		b >>= 1;
	}
	return r;
}

int witness[] = { 2,3,5,7,11 };
bool Miller(ll n)
{
	if (n <= 1) return false;

	for (int a : witness)
	{
		if (a >= n) break;

		ll t = n - 1;
		while (1)
		{
			int64_t at = ModPow(a, t, n);
			if (at == n - 1) break;  // s
			if (t % 2) {
				if (at != 1 && at != n - 1)
					return false;
				break;
			}
			t >>= 1;
		}
	}
	return true;
}


int main()
{
	int T; cin >> T;
	while (T--)
	{
		ll a, b; cin >> a >> b;
		ll S = a + b;

		bool r = true;
		if (S & 0b1) r = Miller(S - 2);
		else r = S > 2;

		cout << (r ? "YES\n" : "NO\n");
	}
}

시간 복잡도

O(\((\log{\mathrm{N}})^3\))

• 단 \(\mathrm{N}=10^{12}\)

설명

말 그대로 알고리즘을 사용하면 된다.

이때 주의점은 10^12 범위의 곱은 long long 범위를 벗어난다는 것이다. 이로인한 오버플로우는 __int128 을 지원하는 환경에서는 문제가 되지 않지만, 그렇지 않다면 위처럼 분할정복을 이용한 모듈러 곱셈을 쓰거나 다른 방법을 사용해야만 한다.

백준에서는 __int128 을 지원한다.