정수론 잡지식

인버스 모듈러

$ A^{-1} \equiv A^{M-2} \pmod{M} $

A^{M-2} 는 분할정복으로 nlogn 으로 구현 가능 (pow는 오버플로 주의)

 

이렇게 하면 이항계수도 해결 가능

$ _{n}\mathrm{C}_{r} \bmod M = \frac{ n! }{ (n-r)! \, r! } \bmod M = ( n! \bmod M ) ( (n-r)! \, r! )^{-1} \bmod M = ( n! \bmod M ) ( (n-r)! \, r! )^{M-2} \bmod M $

 

이항계수 코드

struct Combination {
    ll fact[MAX];
    ll safe_mul(ll a, ll b) { return ((a%MOD) * (b%MOD)) % MOD; }
    void init(int n=MAX) {
        fact[0] = 1;
        for (int i = 1; i < n; ++i) fact[i] = safe_mul(fact[i-1], i);
    }
    ll fast_pow(ll n, ll e) {
        ll ret = 1;
        while (e > 0) {
            if (e % 2) ret = safe_mul(n, ret);
            e /= 2;
            n = safe_mul(n, n);
        }
        return ret;
    }
    ll comb(ll n, ll k) {
        return safe_mul(
                fact[n],
                fast_pow(safe_mul(fact[n-k], fact[k]), MOD-2)
                );
    }
} CM;

 

소수 개수

1e5 이하 : 9 592

1e7 이하 : 664 579

1e9 이하 : 50 847 534

약수

개수 : O( N^{1/3} )

총합 : O( N loglog N )

 

O(sqN) 안에 나이브하게 구할 수 있다.

 

소인수분해

kimhwon.tistory.com/9

 

1e7 이하 소인수 갯수는 7개  (1e8 이상부터는 체 돌리는데도 3초 넘김)