백준 4913번, 페르마의 크리스마스 정리 풀이

문제

백준 4913번

풀이

구간에 해당하는 소수를 빠르게 구하기 위해서,

 

구간 $[1, 100,000,000]$에 해당하는 모든 소수를 에라토스테네스의 체를 사용하여 구해줍니다.

 

해당 구간에 소수를 순서대로 넣으면, 정렬된 상태이기 때문에 이분 탐색을 사용할 수 있습니다.

 

문제 입력에서 주어지는 $[L, U]$에서 $upper(U) - lower(L) $한 수가 소수의 개수가 되겠네요.

 

 

비슷하게 제곱수의 합으로 나타낼 수 있는 수도 위처럼 구할 수 있습니다.

에라토스테네스의 체로 소수($p$)를 구할 때, $(p-1)mod4 = 0$을 만족하는 경우만 따로 관리해주면서, 위처럼 이분 탐색을 사용하여 풀 수 있습니다.

 

다만, $1^1 + 1^1 = 2$가 되는 "짝수인 소수 2"를 따로 고려해야 합니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector <ll> vl;

const ll LIM = 1000000;
vl vis(LIM + 1), prime, euler = {2};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (ll i = 2; i <= LIM; i++) {
		if (vis[i]) continue;
		prime.push_back(i);
		if ((i - 1) % 4LL == 0) euler.push_back(i); //(p-1)%4==0이 되는 경우만 따로 관리
		for (ll j = i; j <= LIM; j += i) vis[j] = 1;
	}

	while (1) {
		ll l, u; cin >> l >> u;
		if (l == -1 && u == -1) break;
		int cnt = upper_bound(all(prime), u) - lower_bound(all(prime), l);
		int ans = upper_bound(all(euler), u) - lower_bound(all(euler), l);
        //이분 탐색을 사용해 구간 내에 존재하는 수들의 개수를 한번에 구할 수 있음
		cout << l << " " << u << " " << cnt << " " << ans << "\n";
	}
}