BOJ 23832 서로소 그래프

문제 링크입니다.

관찰

2부터 N까지의 각 양의 정수 x마다, x 이하의 정수 중 x와 서로소인 것의 개수를 세 모두 더하면 됩니다. 모든 x마다 직접 1부터 x까지 최대공약수를 구해보기에는 시간이 부족합니다.

풀이1

1부터 N까지의 소수를 모두 구해두면 오일러 피 함수를 이용할 수 있습니다.

x 이하의 정수 중 x와 서로소인 것의 개수는, x의 모든 소인수 p에 대해 x에 (p-1)/p를 곱한 값과 같습니다. 소인수끼리는 약수-배수 관계에 별 영향을 못 미치기 때문에, x 이하의 값 중 x의 각 소인수의 배수인 것들을 비율에 따라 제거할 수 있습니다.

풀이2

이쪽이 제 첫 풀인데요. BOJ의 문제 대부분은 제출 가능한 코드 길이의 제한이 524288B입니다.

N = 50000일 때의 답은 10억을 안 넘는 정도입니다. 하나의 N에 대한 답이 커봤자 대강 10글자 정도면 표현 가능하다는 거죠. 그러면 5만 개의 N에 대한 답을 미리 구해서 몽땅 텍스트로 적어도, 그 글자 수가 50만 정도입니다. 아슬아슬하게 BOJ에 제출 가능한 정도의 길이죠.

그래서, 로컬에서 나이브하게 모든 답을 구하는 코드를 짜고 한 5분 방치해 뒀습니다. 그러고 나온 값을 배열에 넣고 입력받은 N에 맞게 출력하기만 하면, 시간 복잡도 $\mathcal{O}(1)$에 문제를 해결할 수 있습니다.

풀이1 - 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1234567890;

bool isp[50505]={1,1};
vector<int> prime;

void compute_prime(int x){
	for(ll i = 2; i <= x; i++){
		if(!isp[i]){
			prime.push_back(i);
			for(ll j = i*i; j <= x; j += i) isp[j] = 1;
		}
	}
	prime.push_back(INF);
}

ll euler_phi(int n){
	ll ret = n;
	for(auto p : prime){
		if(n == 1) return ret;
		if(p > n) break;
		if(!(n%p)){
			ret /= p;
			ret *= p-1;
			while(!(n%p)) n /= p;
		}
	}
	return ret-1;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	ll n; ll ans = 0; cin >> n;
	compute_prime(n);
	for(int i = 2; i <= n; i++) ans += euler_phi(i);
	cout << ans;
}

풀이2 - 코드

#include<iostream>
using namespace std;

int main(){
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int a[50000]={0, 1, 3, 5, 9, 11, 17, 21, 27, 31, (...중략...), 759924263};
	int n;
	cin >> n;
	cout << a[n-1];
}