GCD(n, k) = 1 을 만족하는 [1, n]범위 내에 있는 k의 개수를 구하는 문제다.
소인수 분해로 접근했다.
$45 = 3^{2}$*$5$이므로 3의배수 15개, 5의 배수 9개, 겹치는 개수 3개이므로
45 - 15 - 9 + 3 = 24가 나온다.
하지만 소인수 분해했을 때 $3$*$5$*$7$*$11$*....이런식으로 간다면 겹치는 배수의 개수를 구하는것을
시간내에 해결할 수 없다.
사실 이 문제는 오일러 $\phi$(피 or 파이)함수를 구하는 문제다. (정의 자체가 문제와 동일)
수식을 보니까 정보 보안 강의에서 잠깐 배웠던게 생각이 났다.
오일러 $\phi$함수는 두 가지 성질이 있다.
1) $\phi(ab) = \phi(a)$*$\phi(b)$ ($a,b$는 서로소인 정수)
2) $\phi(p^{m}) = p^{m} - p^{m-1} = p^{m}$*$(1-1/p)$ ($p$는 소수, $m$은 양의 정수)
2)번식에서 $m$이 1이면 $\phi(p) = p-1$이 된다.
소인수 분해를 하고 위의 식을 적용하면 $O(\sqrt[]{N})$에 해결할 수 있다.
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N;
ll mpow(ll x, ll y) {
if (y == 0) return 1LL;
if (y == 1) return x;
if (y & 1) return mpow(x, y - 1) * x;
ll get = mpow(x, y / 2);
return get*get;
}
int main() {
scanf("%lld", &N);
ll ans = 1;
for (ll n = 2;n*n <= N;n++) {
ll cnt = 0;
while (N % n == 0) {
N /= n;
cnt++;
}
if (!cnt) continue;
ans *= mpow(n, cnt) * (n - 1) / n;
}
printf("%lld\n", N == 1 ? ans : ans*(N - 1));
return 0;
}
| cs |
오일러 파이를 안 써봐서요.. ㅠㅠ
답글삭제