본문 바로가기
알고리즘

오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기

by 강성주의 알고리즘 2020. 8. 13.

서로소란

1 을 제외하고 공약수가 없는 두 수의 관계입니다.


오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다.
예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다.
모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다.
예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다.
φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다.
여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다.
즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지 버림)
자연수 n이 하나의 소수의 거듭제곱꼴인 경우는 아래와 같습니다.


φ(9) = φ(3^2) = 9 - 3 = 6개 (1, 2, 4, 5, 7, 8)

만약 n이 a^n * b^m 과 같은 두개 이상의 소수 거듭제곱으로 표현되는 경우는 어떨까요
예를 들어, n = 2^2 * 3^2 인 36인 경우 φ(36)은 2와 3의 최소공배수인 6의 배수들이 중복으로 빠지기 때문에 더해주어야 합니다.


즉 n의 소수들의 각 오일러 피함수 값의 곱이 됩니다.
https://www.acmicpc.net/problem/4355문제는 오일러 피함수를 사용하는 기본 문제입니다.

n이 10억까지 올 수 있으므로 sqrt(n)까지 돌면서 빠르게 소인수 분해가 가능합니다.

 

4355번: 서로소

문제 양의 정수 n이 주어졌을 때, n보다 작은 양의 정수 중에서 n과 서로소인 수 개수를 구하는 프로그램을 작성하시오. 두 정수 a와 b가 서로소가 되려면 x > 1, y > 0, z > 0이면서, a = xy, b= xz를 만족�

www.acmicpc.net

정답 코드.

더보기
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll my_pow(ll a, ll y) {
	ll x = 1;
	while (y) {
		if (y & 1) {
			x *= a;
		}
		a *= a;
		y /= 2;
	}
	return x;
}

ll N;

ll solution() {
	ll n = N;
	ll r = sqrt(n);
	ll answer = 0;
	vector<ll> ack;
	for (ll i = 2; i <= r; i++) {
		ll cnt = 0;
		while (n % i == 0) {
			cnt += 1;
			n /= i;
		}
		if (cnt) {
			if (!answer) {
				answer = 1;
			}
			answer *= (i-1)*my_pow(i, cnt-1);
		}
	}
	if (n > 1) {
		if (!answer) {
			answer = 1;
		}
		answer *= (n - 1);
	}
	return answer;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	while (1) {
		cin >> N;
		if (!N) break;
		cout << solution() << "\n";
	}

}


https://www.acmicpc.net/problem/11689

 

11689번: GCD(n, k) = 1

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

빠른 거듭제곱, 유클리드호제법, 오일러 피함수를 사용하는 문제입니다.

더보기
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
ll pow(ll a, ll y) {
	ll x = 1;
	while (y) {
		if (y & 1) {
			x *= a;
		}
		a *= a;
		y /= 2;
	}
	return x;
}
ll gcd(ll a, ll b) {
	ll c = a%b;
	while (c) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
inline bool is_prime(ll num) {
	ll r = sqrt(num);
	for (ll i = 2; i <= r; i++) {
		if (num % i == 0) return false;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ll n;
	cin >> n;
	if (n == 1) {
		cout << 1;
		return 0;
	}
	ll k = 2;
	ll tn = n;
	vector<ll> ack;
	ll r = sqrt(n);
	for (ll i = 2; i <= r; i++) {
		if (n % i == 0) {
			if (is_prime(i)) {
				ack.push_back(i);
			}
			if (n / i != i && is_prime(n / i)) {
				ack.push_back(n / i);
			}
		}
	}
	if (ack.empty()) { // 소수
		cout << n - 1 << "\n";
		return 0;
	}
	ll ans = 1;
	for (auto nxt : ack) {
		ll cnt = 0;
		for (ll i = 1; i <= 42; i++) {
			ll _p = pow(nxt, i);
			if (_p == gcd(_p, tn)) {
				cnt = i;
			}
			else {
				break;
			}
		}
		ans *= (pow(nxt, cnt) - pow(nxt, cnt - 1));
	}
	cout << ans;

}

 

반응형