서로소란
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)까지 돌면서 빠르게 소인수 분해가 가능합니다.
정답 코드.
#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
빠른 거듭제곱, 유클리드호제법, 오일러 피함수를 사용하는 문제입니다.
#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;
}
'알고리즘' 카테고리의 다른 글
머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 (1) | 2020.08.17 |
---|---|
[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) (0) | 2020.08.17 |
[BOJ] 백준 1028번: 다이아몬드 광산 (0) | 2020.08.12 |
[BOJ] 백준 1027번: 고층 건물 (0) | 2020.08.12 |
[BOJ] 백준 1026번: 보물 (2) | 2020.08.12 |