[BOJ 18151] DivModulo

굉장히 재미있는 문제! 이 문제에서 DivModulo를 정의한다. 표기는 $\mathbb{dmod}$라고 한다. 계산 방법은 다음과 같다. $d \nmid r$라 가정하면

\[r\cdot d^{h} (\mathbb{dmod}\ d) = r \pmod{d}\]

즉, $d$의 거듭제곱을 없애고 모듈러를 구하면 된다. 

 

조합에서 $d$의 소인수들을 모두 제외시킨 뒤 $d$의 거듭제곱을 이룰 수 있는 소인수들만을 제외하고 나머지는 다시 곱해주면 문제 해결! 먼저 주어진 $D$의 소인수들을 모두 찾고 prime power로 나타내자. 앞서 서술한 Modulo Prime Power Trick의 방법을 이용하면 prime power에 대해 조합의 나머지를 구할 수 있다. 다만 값을 리턴할 때 prime power을 곱해주지 않아야 한다. ​리턴된 값은 다른 prime power을 포함하고 있으므로 다른 prime power로 나눠준다. 그럼 각 소인수별로 조합에서 $D$의 소인수가 모두 제거된 합동식을 얻는다. 이를 중국인의 나머지 정리로 합쳐준 뒤에 $D$의 거듭제곱을 이루지 못한 소인수들을 곱해주자. 그럼 답을 얻는다. 

 

# 코드 보기

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll fpow(ll n, ll k, ll mod = 0){
    ll s = 1;
    for(;k;k >>= 1){
        if(mod){
            if(k & 1) s = (__int128) s * n % mod;
            n = (__int128) n * n % mod;
        }
        else{
            if(k & 1) s = s * n;
            n = n * n;
        }
    }
    return s;
}
ll power;
ll factorial_p(ll n, ll p, ll pq, ll bpq){
    ll ret = 1, t, i;
    while(n){
        t = n % pq;
        if(p != 2 && (n / pq) % 2) ret = pq - ret;
        ret = (__int128) ret * fpow(power, t / bpq, pq) % pq;
        for(i = t / bpq * bpq + 1;i <= t;i++){
            if(i % p == 0) continue;
            ret = (__int128) ret * i % pq;
        }
        n /= p;
    }
    return ret;
}
ll bincoeff_pq(ll n, ll m, int p, int q){
    ll real = fpow(p, q);
    if(q % 2) q += 1; //match with even number
    ll pq = fpow(p, q), bpq = fpow(p, q / 2);
    if(p == 2){
        pq = fpow(p, max(4, q));
        bpq = fpow(p, max(4, q) / 2);
    }
    ll gop = 1, i;
    ll up, dn, ans, get;
    for(i = 1;i < bpq;i++){
        if(i % p == 0) continue;
        gop = (__int128) gop * i % pq; 
    }
    power = gop;
    get = factorial_p(n, p, pq, bpq);
    up = get;
    get = factorial_p(m, p, pq, bpq);
    dn = get;
    get = factorial_p(n - m, p, pq, bpq);
    dn = (__int128) dn * get % pq;
    ans = (__int128) up * fpow(dn, pq / p * (p - 1) - 1, pq) % pq;
    return (__int128) ans % real;
}
 
int factorize(int p[][3], int n){
    int pt = 0, i = 2;
    while(i * i <= n){
        if(n % i == 0){
            p[pt][0] = i;
            p[pt][2] = 1;
            while(n % i == 0){
                n /= i;
                p[pt][1]++;
                p[pt][2] *= i;
            }
            pt++;
        }
        if(i == 2) i = 1;
        i += 2;
    }
    if(n - 1){
        p[pt][0] = n;
        p[pt][1] = 1;
        p[pt][2] = n;
        pt++;
    }
    return pt;
}
 
ll CRT(int p[][3], ll *a, int len, int mod){
    int i;
    ll ret = 0;
    for(i = 0;i < len;i++){
        ll k = mod / p[i][2];
        ll phi = p[i][2] / p[i][0] * (p[i][0] - 1);
        ret = (ret + a[i] * k % mod * fpow(k, phi - 1, mod) % mod) % mod;
    }
    return ret;
}
 
ll p_time(ll n, int p){
    ll ret = 0;
    while(n){
        ret += n / p;
        n /= p;
    }
    return ret;
}
 
int p[11][3];
ll pt[11], a[11], ptime[11];
int main(){
    ll n, m, mi = 1e9, k;
    int d, len, i, j;
    scanf("%lld %lld %d", &n, &m, &d);
    len = factorize(p, d);
    for(i = 0;i < len;i++){
        ptime[i] = p_time(n, p[i][0]) - p_time(m, p[i][0]) - p_time(n - m, p[i][0]);
        mi = min(mi, ptime[i] / p[i][1]);
        pt[i] = fpow(p[i][0], ptime[i]);
    }
    for(i = 0;i < len;i++){
        a[i] = bincoeff_pq(n, m, p[i][0], p[i][1]);
        ll t = 1;
        for(j = 0;j < len;j++){
            if(j == i) continue;
            t = t * pt[j] % p[i][2];
        }
        ll phi = p[i][2] / p[i][0] * (p[i][0] - 1);
        a[i] = a[i] * fpow(t, phi - 1, p[i][2]) % p[i][2];
    }
    k = CRT(p, a, len, d);
    for(i = 0;i < len;i++){
        k = k * fpow(p[i][0], ptime[i] - mi * p[i][1], d) % d;
    }
    printf("%lld", k);
}

# 닫기