백준 23832: 서로소 그래프

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

23832번: 서로소 그래프

 

코드

#include <bits/stdc++.h>
 
using namespace std;
#define ull unsigned long long int
ull Power(__int128 x, __int128 y, __int128 mod) {
    x %= mod;
    ull ret = 1;
    while(y > 0) {
        if(y%2 == 1) ret = (ret*x)%mod;
        x = (x*x)%mod;
        y /= 2;
    }
    return (ull)ret;
}
 
bool miller(ull n, ull a){
    if(a % n == 0) return true;
    ull k = n-1;
    while(true){
        ull temp = Power(a, k, n);
        if(temp == n-1) return true;
        if(k%2) return (temp == 1 || temp == n-1);
        k /= 2;
    }
}
ull GCD(ull a, ull b) {
    if(a < b) swap(a, b);
    while (b != 0) {
        ull r = a%b;
        a = b;
        b = r;
    }
    return a;
}
bool isPrime(ull n) {
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0) return false;
    for (int iter: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
         if(!miller(n, iter)) {
            return false;
            break;
        }
    }
    return true;
}
 
ull findDiv(__int128 n) {
    if(n%2 == 0) return 2;
    if(isPrime(n)) return n;
 
    __int128 x = rand()%(n-2) + 2, y = x, c = rand()%10 + 1, g = 1;
    while(g == 1) {
        x = (x*x%n + c)%n;
        y = (y*y%n + c)%n;
        y = (y*y%n + c)%n;
        g = GCD(abs(x-y), n);
        if(g == n) return findDiv(n);
    }
    if(isPrime(g)) return g;
    else return findDiv(g);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    ull p, res = 0;
    cin >> p;
    for (int i = 1; i <= p; i++) {
        ull ans = 1;
        map<ull, ull> m;
        int ii = i;
        while(ii > 1) {
            ull div = findDiv(ii);
            if (m.find(div) != m.end()) m[div]++;
            else m[div] = 1;
            ii /= div;
        }
        for (auto iter : m) {
            if (iter.second > 1) ans *= pow(iter.first, iter.second) - pow(iter.first, iter.second - 1);
            else ans *= iter.first - 1;
        }
        res += ans;
    }
    cout << res - 1; return 0;
}

---

사용된 알고리즘

 

밀러-라빈 소수 판별법, 오일러 피 함수, 폴라드 로 알고리즘

---

풀이

오일러 피 함수의 특징인 Φ(mn) = Φ(m)Φ(n)과 Φ(p^a) = p^a - p^a-1 = p^a(1 - 1/p)를 알아야 풀 수 있는 문제입니다.

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    ull p, res = 0;
    cin >> p;
    for (int i = 1; i <= p; i++) {
        ull ans = 1;
        map<ull, ull> m;
        int ii = i;
        while(ii > 1) { // 소인수를 구하는 폴라드 로 알고리즘입니다.
            ull div = findDiv(ii);
            if (m.find(div) != m.end()) m[div]++; // 이미 나온 소인수라면 개수를 카운트 합니다.
            else m[div] = 1; // 처음 나오는 소인수이면 map에 저장해줍니다.
            ii /= div;
        }
        for (auto iter : m) { 
            if (iter.second > 1) ans *= pow(iter.first, iter.second) - pow(iter.first, iter.second - 1); // Φ(p^a) = p^a - p^a-1 = p^a(1 - 1/p)
            else ans *= iter.first - 1; // Φ(mn) = Φ(m)Φ(n)
        }
        res += ans;
    }
    cout << res - 1; return 0;
}