[BOJ 13714] 약수의 개수

위 문제에서 구하고자 하는 것은 다음과 같다.

$$\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} \tau(ijk)$$

필요한 이론을 증명하고 문제를 해결하자.

 

Theorm 1. $$\tau(ij)=\sum_{x|i} \sum_{y|j} [x \perp y]$$

 

Lemma 1.

$$n=\prod_{i=0}^{k} p_{i}^{a_{i}}t\ \ (p_{i} \nmid t)$$

일 때 다음은 $n$의 약수 중 $p_{i}$들의 배수의 개수이다.

$$\prod_{i=0}^{k} a_{i} \tau(t)$$

 

$i=p^{a}s(p \nmid s),\ j=p^{b}t(p \nmid t)$라 가정하자. 

$$\tau(ij)=(a+b+1)\tau(st)$$

$s, t$가 서로소가 아니므로 위 과정을 반복해주자.

$$\tau(ij)=(a_{0}+b_{0}+1)(a_{i}+b_{i}+1)\tau(s_{1}t_{1})=\prod_{i=0}^{k} (a_{i}+b_{i}+1) \tau(s_{k})\tau(t_{k})$$

$\gcd(s_{k},t_{k})=1$이다. 마찬가지 방법으로 $\tau(i), \tau(j)$를 전개하자.

$$\tau(i)=\prod_{i=0}^{k} (a_{i}+1)\ \tau(s_{k})$$

$$\tau(j)=\prod_{i=0}^{k} (b_{i}+1)\ \tau(t_{k})$$

$$\tau(i)\tau(j)=\prod_{i=0}^{k} (a_{i}b_{i}+a_{i}+b_{i}+1)\ \tau(s_{k})\tau(t_{k})$$

$\tau(ij)$는 $\tau(i)\tau(j)$에서 $a_{i}b_{i}$라는 항이 빠진 형태이다. 이것은 $i, j$의 약수를 각각 $x, y$라 했을 때 $x, y$를 동시에 나누는 소수 $p$가 존재하는 $x, y$ 쌍의 개수를 약수의 곱에서 제외시켜야 함을 의미한다. 즉, 다음과 같이 쓸 수 있다.

 

보충 설명(클릭하세요)

$a_{i}\tau(s_{k})b_{i}\tau(t_{k})$이고 이 항이 사라진 것이므로 Lemma 1에 의해 동시에 $p_{i}$으로 나누어 떨어지는 약수가 제외됨을 확인할 수 있다. 

 

$$\sum_{x|i} \sum_{y|j} 1 - \sum_{x|i} \sum_{y|j}[\gcd(x,y)>1]$$

$$\sum_{x|i} \sum_{y|j} [\gcd(x,y)=1] = \sum_{x|i} \sum_{y|j} [x \perp y]$$

 

위 과정은 $i, j$ 2개인 경우를 진행했다. 3개인 경우는 위의 경우에서 $i$ 또는 $j$를 더 쪼개면 된다.

$$\tau(ijk)=\sum_{x|i} \sum_{y|j} \sum_{z|k} [x \perp y] [y \perp z] [z \perp x]$$

 

 가장 처음의 식을 다음과 같이 변형한다.

$$\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} \sum_{x|i} \sum_{y|j} \sum_{z|k} [x \perp y] [y \perp z] [z \perp x]$$

순서를 바꾼다.

$$\sum_{x=1}^{a} \sum_{y=1}^{b} \sum_{z=1}^{c} \left[a/x\right]\left[b/y\right]\left[c/z\right] [x \perp y] [y \perp z] [z \perp x]$$

$$\sum_{x=1}^{a} \left[a/x\right] \sum_{y=1}^{b} \left[b/y\right] [x \perp y] \sum_{z=1}^{c} \left[c/z\right] [x \perp z] \sum_{d|y,z} \mu(d)$$

$y=dp, z=dq$라 두자.

$$\sum_{x=1}^{a} \left[a/x\right] \sum_{d=1}^{\min(b,c)} \mu(d) [x \perp d] \sum_{p=1}^{\left[b/d\right]} \left[b/dp\right] [x \perp p] \sum_{q=1}^{\left[c/d\right]} \left[c/dq\right] [x \perp q]$$

$$W(s, t)=\sum_{i=1}^{s} \left[s/i\right] [t \perp i]$$

라 정의한다. 다시 표현하면

$$\sum_{x=1}^{a} \left[a/x\right] \sum_{d=1}^{\min(b,c)} \mu(d) [x \perp d] W(\left[b/d\right], x) W(\left[c/d\right], x)$$

$[x \perp y]$의 누적합을 전처리 한다면 $W$는 $O(\sqrt{s})$안에 계산할 수 있다. $\mu(y) [x \perp y]$의 누적합을 전처리 한다면 $\sum_{d=1}^{\min(b,c)}$를 $O(\sqrt{n})$으로 계산할 수 있다. 따라서 전체 시간 복잡도는 $O(n^{2})$이다.

 

이것을 구현한 코드이다.

코드 보기

#include<stdio.h>
typedef long long ll;
#define sz 2001
ll cop[sz][sz];
ll pre_cop[sz][sz];
ll mu_cop[sz][sz];
ll mu[sz];
ll mod=1<<30;
ll sp[sz];
ll prime[sz],pt;
ll pre_bc[sz];
ll min(ll a,ll b){
    return a>b?b:a;
}
ll W(ll s,ll t){
    ll i,j,sum=0;
    for(i=1;i<=s;i=j+1){
        j=s/(s/i);
        sum+=s/i*(pre_cop[t][j]-pre_cop[t][i-1])%mod;
        sum%=mod;
    }
    return sum;
}
int main(){
    ll i,j,k;
    for(i=1;i<sz;i++){
        for(j=1;j<sz;j++) cop[i][j]=1;
    }
    for(i=2;i<sz;i++){
        ll h=i;
        for(j=2;j*j<=h;j++){
            if(h%j==0){
                for(k=j;k<sz;k+=j){
                    cop[i][k]=0;
                }
                while(h%j==0) h/=j;
            }
        }
        if(h-1){
            for(j=h;j<sz;j+=h) cop[i][j]=0;
        }
        for(j=1;j<sz;j++) pre_cop[i][j]=cop[i][j]+pre_cop[i][j-1];
    }
    for(i=1;i<sz;i++){
        pre_cop[1][i]=cop[1][i]+pre_cop[1][i-1];
    }
    mu[1]=1;
    for(i=2;i<sz;i++){
        if(!sp[i]){
            prime[pt++]=i;
            mu[i]=-1;
        }
        for(j=0;j<pt;j++){
            if(i*prime[j]>sz) break;
            sp[i*prime[j]]=1;
            if(i%prime[j]==0) break;
            mu[i*prime[j]]=mu[i]*mu[prime[j]];
        }
    }
    for(i=1;i<sz;i++){
        for(j=1;j<sz;j++){
            mu_cop[i][j]=mu[j]*cop[i][j]+mu_cop[i][j-1];
        }
    }
    ll a,b,c,sum=0;
    scanf("%lld %lld %lld",&a,&b,&c);
    for(i=1;i<=min(b,c);i=pre_bc[i]+1){
        pre_bc[i]=min(b/(b/i),c/(c/i));
    }
    for(i=1;i<=a;i++){
        ll s=0;
        for(j=1;j<=min(b,c);j=k+1){
            k=pre_bc[j];
            s+=W(b/j,i)*W(c/j,i)%mod*(mu_cop[i][k]-mu_cop[i][j-1])%mod;
            s%=mod;
        }
        sum=(sum+s*(a/i)%mod)%mod;
    }
    printf("%lld",sum);
}