[BOJ 1770] 배수와 약수의 개수

문제는 다음과 같습니다.

양의 정수 $n$이 주어졌을 때, 다음 두 조건을 만족하는 양의 정수 $x$의 개수를 구해보자.
- $x$는 $n$의 배수이다
- $x$의 양의 약수의 개수는 $n$개이다.

 

$x$가 $n$의 배수이니 적어도 $x$는 $n$의 소인수들을 모두 갖고 있습니다. 

$n=p^{c}$($p$는 임의의 소수, $c$는 임의의 자연수)라고 해봅시다. 만약 임의의 소수 $q$에 대해 $x=p^{p^{c-1}-1}q^{p-1}$이라면 $q$를 마음껏 정할 수 있기 때문에 경우가 무한개가 될 것입니다. 이를 만족하기 위해서는 $p^{c-1}-1 \ge c$이면 됩니다. 가장 작은 소수인 2에 대해서 생각해봅시다. $2^{c-1} \ge c+1$을 만족해야 합니다. 이 부등식은 $c=3$일 때부터 성립합니다.  [부등식이 성립하지 않는다] = [값이 유한하다] 로 생각할 수 있습니다. $n=2^{2}, 2$일 경우 값이 유한하겠군요. 이제 $p=3$인 경우를 생각해봅시다. $3^{c-1} \ge c+1$입니다. $c \ge 2$일 때 성립합니다. $p \ge 3$인 경우는 항상 $c \ge 2$인 경우에 성립합니다. 

 

지금까지 $n=p^{c}$인 경우를 다루어 보았습니다.

그럼 $n$을 이루는 소수의 개수가 늘어나는 경우에는 어떻할까요?

$n=p^{c}q^{d}$($p,q$는 임의의 소수, $c,d$는 자연수)라고 해봅시다. $p^{c}-1 \ge c$라는 사실은 명백합니다. 그러니 임시적으로 $x=p^{p^{c}-1}q^{d}$로 쓸 수 있을 것입니다. 남은 일은 $q$의 지수 값을 변형해서 $q^{d}$을 맞추는 일 뿐입니다. 이 일은 앞서 진행한 과정 $n=p^{c}$일 때와 똑같습니다. 이것은 $n$을 이루는 소수의 개수가 많아지더라고 항상 성립합니다. 즉, $n$을 소인수분해한 결과에서 각 소수들의 거듭제곱 중 하나라도 $n=p^{c}$일 때 값이 무한할 조건을 가지게 된다면 $n$은 무한한 경우를 가지게 됩니다.

 

이제 값이 유한한 것 끼리의 곱을 생각해야 할 때가 왔습니다.

$n=2^{2}p$($p$는 소수)일 경우 $x=2^{p-1}pq$($q$는 소수)가 된다면 성립합니다. 이때 $q$를 어떤 소수로 잡아도 상관없기 때문에 값이 무한하게 됩니다. 따라서 $n$이 4가 아닌 $4k$($k$는 자연수)의 꼴이 된다면 경우가 무한해 집니다.

$n=pq$($p,q$는 소수)이면 $x=pq\cdot k$($k$는 임의의 자연수)이고 $k$는 $p,q$이외의 소수 인수를 가질 수 없습니다.

약수의 개수가 $pq$가 되어야 하는데  인수분해는 유일하게 $pq=p\cdot q$ 하나뿐입니다.

따라서 $x$가 가질 수 있는 유일한 소인수의 개수는 2개입니다. $p$의 지수가 $q-1$이거나 $p-1$일 수 있습니다. 즉 $2!$이 $x$의 개수입니다. 일반화 하자면 $n$의 소인수 개수를 $p$라고 할 때 조건을 만족하는 $x$의 개수는 $p!$개입니다.

$n=2^{2}$인 경우 이를 만족하는 $x$는 $2^{3}$하나 뿐이라는 것을 확인할 수 있습니다.

 

위와 같은 사실을 확인하려면 $n$을 빠르게 인수분해 할 수 있는 Pollard Rho 알고리즘을 써야겠죠!

모든 조건을 구현한 코드입니다.

 

# 코드 보기

#include<stdio.h>
#include<stdlib.h>
typedef long long int lo;
lo s[40000];
lo fpow(lo n,lo k,lo p){ //빠른 거듭제곱 
    lo s=1;
    for(;k;k>>=1){
        if(p){
            if(k&1) s=(__int128)s*n%p;
            n=(__int128)n*n%p;
        }
        else{
            if(k&1) s=(__int128)s*n;
            n=(__int128)n*n;
        }
    }
    return s;
}
 
lo miller(lo n,lo a){ //밀러 라빈 소수 판정 
    lo t=n-1;
    while(t%2==0) if(fpow(a,t/=2,n)==n-1) return 1;
    t=fpow(a,t,n);
    return t==n-1 || t==1;
}
lo prime(lo n){
    if(n==1) return 0;
    int m=12,i;
    lo a[12]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for(i=0;i<m;i++){
        if(a[i]==n) return 1;
        if(!miller(n,a[i])) return 0;
    }
    return 1;
}
lo gcd(lo a,lo b){ //최대공약수 
    return b?gcd(b,a%b):a;
}
lo rf(lo x,lo n){ //폴라드 로에서 쓸 신기한 값 
    return ((__int128)x*x+13)%n;
}
lo pollard_rho(lo n){ //폴라드 로 알고리즘 
    lo x=2,y=2,t=1,c=13;
    if(prime(n)) return n;
    if(n%2==0) return 2;
    while(t==1 || t==n){
        x=rf(x,n);
        y=rf(rf(y,n),n);
        t=gcd(x>y?x-y:y-x,n);
        if(t==n) x=y=rand()%n;
    }
    return prime(t)? t:pollard_rho(t);
}
lo factorize(lo n){ //소인수분해 
    lo r,i,j,p=0;
    while(n-1){
        r=pollard_rho(n);
        n/=r;
        s[p++]=r;
    }
    for(i=0;i<p;i++){
        for(j=0;j<p-i-1;j++){
            if(s[j]>s[j+1]){
                lo t=s[j];
                s[j]=s[j+1];
                s[j+1]=t;
            }
        }
    }
    return p;
}
lo fac(lo k){
    lo i,s=1;
    for(i=2;i<=k;i++){
        s=(__int128)s*i;
    }
    return s;
}
int main(){
    int t,i;
    lo j,n;
    scanf("%d",&t);
    for(i=0;i<t;i++){
        lo prv=0,ans=0,p=0;
        scanf("%lld",&n);
        if(n==4 || n==1){
            printf("1\n");
            continue;
        }
        p=factorize(n);
        prv=s[0];
        for(j=1;j<p;j++){
            if(prv==s[j]){
                ans=-1;
                break;
            }
            else{
                prv=s[j];
            }
        }
        if(!ans){
            ans=fac(p);
        }
        for(j=0;j<p;j++) s[j]=0;
        printf("%lld\n",ans);
    }
}

# 닫기