백준 4355번 서로소

< 백준 4355번 서로소 - 마포 코딩박 >

사용한 알고리즘: 수학


 양의 정수 n 이 주어질 때, n 보다 작은 n과 서로소인 양의 정수의 수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (수학)
 1. 소수 p 의 서로소의 개수 = §(p) = p^k - (1-1/p)  입니다.
 ( 오일러 함수 기호를 찾을수가 없어서 § 로 대체합니다... )
 2. a,b가 서로소일 때, §(ab) = §(a)*§(b)  입니다.
 이를 이용해 주어진 n을 소인수 분해 하여 서로소 개수를 찾습니다.

(2) (코드 24~29, 10~22)
 1~40000 까지의 소수를 미리 구해 n을 소인수 분해 합니다.
 ( 어떤 수 A 는 root(A) 초과의 소수로는 나누어 지지 않습니다. n은 최대 10^9 입니다. )

(3) (코드 30~45)
 과정 (1)에 따라 서로소 개수를 찾습니다.
 예를들어 §(n) = §(a^2*b^3) = §(a)*§(b) = ( a^(2-1)*(a-1) )*( b^(3-1)*(b-1) ) 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 40000;
	typedef long long ll;
	int N;
	map<int, int> Construct;
	vector<int> Prime;
	bool visited[MAX];
	// 소인수 분해
	void MakeCon(int x){
	if(x==1) return;
	for(auto P: Prime){
	if(x%P==0){
	Construct[P]++;
	MakeCon(x/P);
	return;
	}
	}
	// 남아있으면 걔도 소수
	if(x!=1) Construct[x]++;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 소수 만들어 놓기
	for(int i=2; i<MAX; ++i){
	if(visited[i]) continue;
	Prime.push_back(i);
	for(int j=2*i; j<MAX; j+=i) visited[j] = true;
	}
	while(1){
	cin >> N;
	if(N==0) break;
	Construct.clear();
	MakeCon(N);
	long long ans = 1LL;
	for(auto iter: Construct){
	int num = iter.first;
	int cnt = iter.second;
	// 오일러(p^k) = p^k x (1-1/p) = p^(k-1) x (p-1)
	cnt--;
	while(cnt--) ans*=num;
	ans*=(num-1);
	}
	cout << ans << '\n';
	}
	return 0;
	}

view raw BOJ 4355.cpp hosted with ❤ by GitHub