백준: Class 6 - 11689, 13977

</br> 클래스 6 계속
</br>

11689: GCD(n, k) = 1

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

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;

    long long ans = 1;

    for(long long i = 2; i*i <= n; i++){
        long long cnt = 0;
        while( n % i == 0 ){
            n /= i;
            cnt++;
        }
        if( cnt ){
            ans *= pow(i, cnt-1);
            ans *= i - 1;
        }
    }
    if( n - 1 ) ans *= n - 1;

    cout << ans << endl;

}

서로소의 개수를 구하는 문제
이산수학 때였나 오일러 파이 함수를 배웠던 기억이 있어서… 찾아 보고 구현했다

n = A^a * B^b * ... * Z^z라면
phi(n) = (A^a - A^(a-1)) * (B^b - B^(b-1)) * ... * (Z^z - Z^(z-1))
       = A^(a-1)*(A - 1) * B^(b-1)*(B - 1) * ... * Z^(z-1)*(Z - 1)

포문 안에 i를 long long으로 안 하고 int로 해서 시간 초과 났었다 바보
</br>

13977: 이항 계수와 쿼리

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

방법 1.

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

long long fact[4000001];

long long mypow(long long a, int b){
    if( b == 1 ) return a;
    if( b % 2 ) return a*mypow(a, b-1) % MOD;
    long long aa = mypow(a, b/2) % MOD;
    return aa*aa % MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    cin >> m;

    fact[0] = 1;
    for(int i = 1; i <= 4000000; i++){
        fact[i] = fact[i-1] * i % MOD;
    }

    while( m-- ){
        int n, k;
        cin >> n >> k;
        long long p = fact[k] * fact[n-k] % MOD;
        cout << fact[n] * mypow(p, MOD-2) % MOD << '\n';
    }

}

m이 최대 100000인데 시간 제한이 1초 이므로, 짱 빨리 해야 하네
다행히도, n이 400만까지므로 미리 팩토리얼을 구해 놓을 수 있겠다

그래서 돌려 봤는데 20C10이 0으로 나온다!!

20 10

n!        k!      (n-k)!
146326063 3628800 3628800

아하 n!가 모듈러 된 상황이니까 더 작을 수 있어서 안 되는구나 생각해보니 당연함
곱셈 역원을 구해 줘야 하는구나

13172: Σ(https://cyj893.github.io/algorithm/Algorithm16_8/)에서도 다뤄 봤듯이 b^(X-2) ≡ b^(-1) (mod X) 이므로, 빠르게 pow()를 구현해서 역원을 곱해 주면 된다.

방법 2.

    inverse[4000000] = mypow(fact[4000000], MOD-2);
    for(int i = 3999999; i >= 0; i--){
        inverse[i] = inverse[i+1] * (i+1) % MOD;
    }

그런데 이렇게 dp로 역원을 미리 다 구해놓는 코드를 봤는데, 어떻게 이런 식이 나온 걸까

i!의 역원 = (i+1)!의 역원 * (i+1) mod 1000000007
i!^(MOD-2) = (i+1)!^(MOD-2) * (i+1) mod 1000000007
i!^(MOD-2) = i!^(MOD-2) * (i+1)^(MOD-2) * (i+1) mod 1000000007
i!^(MOD-2) = i!^(MOD-2) mod 1000000007

오… 이런 신기한 일이
정말 가능하네

inv[1] = 1;
for (int i=2; i<p; ++i)
	inv[i] = (p - (p/i) * inv[p%i] % p) % p;

https://codeforces.com/blog/entry/5457
구글 검색해서 봤는데 1~n, mod p 구하기에 이런 것도 있단다
</br>

---

은근히 이산 수학이나 그럴 때 배운 게 쓰인다
</br>