[BOJ 18559] Call It What You Want

이 문제는 $x^{n}-1$을 소인수분해 하는 것이 목적이다. 문제 지문에 나와있다시피 $x^{n}-1$은 다음과 같이 소인수분해 된다. 

\[x^{n}-1=\prod_{d|n} \Phi_{d}\]

양 변에 log를 취하자. 

\[\log(x^{n}-1)=\sum_{d|n} \log(\Phi_{d})\]

뫼비우스 역공식을 이용하면

\[\log(\Phi_{n})=\sum_{d|n} \log(x^{d}-1) \mu(n/d)\]

\[\Phi_{n}=\prod_{d|n} (x^{d}-1)^{\mu(n/d)}\]

위 식을 이용해 $x^{n}-1$을 구성하는 각각의 $\Phi$들을 구하면 답을 구할 수 있다. 

 

$\mu(n/d)$의 값이 1 또는 -1인 것만 계산하면 된다. 물론 $\mu$를 전처리 하는 것은 필수이다. 1인 것들은 미리 전부 곱해두자. 그 다음 -1인 것들로 나누면 $\Phi$값을 구할 수 있다. $x^{d}-1$를 곱하거나, $x^{d}-1$로 나누는 연산은 빠르게 처리할 수 있다. 각각 $P(x)$에 연산을 적용한다고 하면

$x^{d}-1$을 곱하는 과정은 $P(x)$를 $d$칸 당기고 $P(x)$를 한 번 빼면 된다.

$x^{d}-1$로 나누는 과정은 $P(x)$의 나머지 $R(x)$를 $x^{d} \equiv 1 \pmod{x^{d}-1}$을 이용해 구한 뒤 $P(x)-R(x)$를 $x^{d}-1$로 나누어주면 된다.

곱하는 연산, 나누는 연산 모두 $P(x)$의 길이가 $m$이라 했을 때 $O(m)$시간으로 해결할 수 있다.

사실 위의 연산을 구현하려고 FFT도 쓰고 빠른 다항식의 나눗셈도 썼는데 위 방법이 가장 빠르다 😥

$\Phi$를 구하는 것은 $O(m\sqrt{n})$시간이며 $x^{n}-1$을 구성하는 모든 $\Phi$를 구하는 것은 $O(nm)$이 걸린다.

$m$이 작아서 사실상 $O(n)$으로 보면 될 것 같다.

마지막에 정렬하는 부분은 naive하게 짜도 된다. 설마 $\Phi$ 개수가 1000개를 넘갰어!

사실상 풀이는 별 것이 없다. 날먹인가? 🤔

 

아래는 이 모든 과정을 구현한 코드이다.

# 코드 보기

#include<stdio.h>
#include <vector>
#include <algorithm>
#define MAX 100000
 
using namespace std;
typedef vector<int> poly;
 
int mu[MAX+1];
int sp[MAX+1];
poly up;
vector<poly> phis;
vector<int> down;
 
void gop(poly &a,int d,int* pt){
    int i;
    for(i=*pt;i>=0;i--){
        a[i+d]+=a[i];
        a[i]*=-1;
    }
    *pt+=d;
}
 
void divide(poly &a,int d){
    poly q;
    int i;
    q.resize(a.size());
    for(i=a.size()-1;i>=d;i--) a[i%d]-=a[i];
    for(i=a.size()-1;i>=d;i--){
        a[i-d]+=a[i];
        q[i-d]+=a[i];
        a[i]=0;
    }
    for(i=q.size()-1;i>=0;i--)if(q[i]) break;
    q.resize(i+1);
    a=q;
}
 
void phi(int n){
    int i,pt_u=0;
    up.clear();up.resize(2*MAX+1);
    down.clear();
    up[0]=1;
    
    for(i=1;i*i<=n;i++){
        if(n%i==0){
            if(mu[n/i]==1) gop(up,i,&pt_u);
            if(mu[n/i]==-1) down.push_back(i);
            if(n!=i*i){
                if(mu[i]==1) gop(up,n/i,&pt_u);
                if(mu[i]==-1) down.push_back(n/i);
            }
        }
    }
 
    up.resize(pt_u+1);
    for(i=0;i<down.size();i++) divide(up,down[i]);
    phis.push_back(up);
}
 
void print(poly &a){
    int i,k=a.size()-1;
    printf("(");
    for(i=k;i>=0;i--){
        if(!a[i]) continue;
        int t=a[i];
        if(i!=k){
            if(t<0) printf("-",t*=-1);
            else printf("+");
        }
        if(t!=1) printf("%d",t);
        if(i>1) printf("x^%d",i);
        if(i==1) printf("x");
        if(i==0 && t==1) printf("%d",t);
    }
    printf(")");
}
 
int cmp(const poly &a,const poly &b){
    int as=a.size()-1,bs=b.size()-1;
    if(as==bs){
        while(as>=0){
            as--;bs--;
            if(a[as]!=b[bs]) return a[as]>b[bs];
        }
    }
    return as>bs;
}
 
void k_sort(){
    int sz=phis.size(),i,j;
    for(i=0;i<sz;i++){
        for(j=0;j<sz-i-1;j++){
            if(cmp(phis[j],phis[j+1])){
                poly t=phis[j];
                phis[j]=phis[j+1];
                phis[j+1]=t;
            }
        }
    }
}
 
int main(){
    int i,j;
    for(i=1;i<=MAX;i++) mu[i]=1;
    sp[1]=1;
    for(i=2;i<=MAX;i+=2){
        if(sp[i]) continue;
        for(j=i;j<=MAX;j+=i){
            if(j!=i) sp[j]=1;
            if(j%(i*i)==0) mu[j]=0;
            else mu[j]*=-1;
        }
        if(i==2) i=1;
    }
    
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=1;i*i<=n;i++){
            if(n%i==0){
                phi(i);
                if(i*i!=n) phi(n/i);
            }
        }
        k_sort();
        for(i=0;i<phis.size();i++) print(phis[i]);
        phis.clear();
        printf("\n"); 
    }
}

# 닫기