[BOJ 16808] Identity Function

함수 $f$는 다음과 같이 정의된다.

\[f(a)=a^{N} \pmod{N}\]

\[F_{1}(a)=f(a)\]

\[F_{k+1}(a)=F_{k}(f(a)) (k=1,2,3,...)\]

이를 간단히 하면 다음과 같다.

\[F_{k}(a)=a^{N^{k}} \pmod{N}\]

이때 $F_{k}(a)=a$인 최소의 $k$를 찾는 것이 우리의 목표이다.

 

먼저 $N=p$(소수)일 경우를 생각해보자.

\[a^{N^{k}} \equiv a \pmod{N}\]

이때 $gcd(a,N)=1$이므로 

\[a^{N^{k}-1} \equiv 1 \pmod{N}\]

\[N^{k} \equiv 1 \pmod{\phi(N)}\]

만약 이때 $\gcd(N,\phi(N))=1$이 아니라면 만족하는 $k$가 존재하지 않는다. $k$가 존재한다면 그 값은 $\phi(\phi(N))$이다.

 

$N=p^{2}l$($p \nmid l$,$p$는 소수)일 경우를 보자. 

$\gcd(a,N)=1$이면 

\[a^{N^{k}-1} \equiv 1 \pmod{N}\]

\[N^{k} \equiv 1 \pmod{\phi(N)}\]

이때 $\gcd(N, \phi(N))>1$이므로 만족하는 $k$가 없다. $a$가 $N$과 서로소가 아닐 경우를 확인하는 것은 의미가 없다.(모든 자연수 $a$에 대해 성립하는 $k$여야 한다.) 

 

이제 남은 경우는 여러 소수들이 한 번씩 곱해진 경우다. 

$N=p_{1}p_{2}...p_{m}$이라 두자.($p_{i}$은 소수, $m$은 자연수) $\gcd(a,N)=\alpha$라 둔다면 $\phi(\phi(N/\alpha))$와 $N$이 서로소일 경우 $k=\phi(\phi(N/\alpha))$이고 아닐 경우 $k$는 존재하지 않는다.

 

$N$의 소인수를 찾고 $\alpha$ 값을 $N$의 가능한 모든 소인수의 곱으로 설정하면서 $k$ 값을 찾아나가면 된다. $k$가 문제의 조건을 만족한다면 $uk$($u$는 자연수)역시 문제의 조건을 만족하므로 여러개의 $k$가 나온다면 그들의 최소공배수를 구해주면 된다. 앞서 한 논의에 의해 구해진 $k$값은 최솟값이 아닐 수 있다. 따라서 $k$의 소인수를 구하여 $k$의 크기를 줄여가며 $1$부터 $\sqrt{N}$까지의 $a$에 대해 식이 성립하는지 확인하면 최솟값을 구할 수 있다. $\sqrt{N}$까지의 값 만으로 판별할 수 있는지의 여부는 나도 모른다^^.

 

# 코드 보기

#include<stdio.h>
typedef long long ll;
ll solve(ll n,ll m);
ll fpow(ll n,ll k,ll mod){
    ll s=1;
    for(;k;k>>=1){
        if(k&1) s=s*n%mod;
        n=n*n%mod;
    }
    return s;
}
ll phi(ll n){
    ll s=1,i;
    for(i=2;i*i<=n;i+=2){
        if(n%i==0){
            n/=i;
            s*=i-1;
            while(n%i==0){
                n/=i;
                s*=i;
            }
        }
        if(i==2) i--;
    }
    if(n-1) s*=n-1;
    return s;
}
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll p[50],ch[50],pt;
ll f(ll n,ll v,ll d){
    if(d==pt) return 1;
    if(v==pt){
        ll s=1,i,m=1;
        for(i=0;i<pt;i++){
            if(ch[i]) continue;
            s*=p[i]-1;
            m*=p[i];
        }
        ll g=gcd(n,s);
        if(g>1) return -1;
        ll k=phi(s),l,arr[50],ptt=0;
        l=k;
        for(i=2;i*i<=l;i+=2){
            if(l%i==0){
                arr[ptt++]=i;
                while(l%i==0) l/=i;
            }
            if(i==2) i--;
        }
        if(l-1) arr[ptt++]=l;
        for(i=0;i<ptt;i++){
            while(k%arr[i]==0 && fpow(n,k/arr[i],s)==1) k/=arr[i];
        }
        return k;
    }
    ll mi=1,i,t;
    for(i=0;i<2;i++){
        ch[v]=i;
        if(i==0) t=f(n,v+1,d+1);
        else t=f(n,v+1,d);
        if(t==-1) return -1;
        mi=mi*t/gcd(mi,t);
    }
    ch[v]=0;
    return mi;
}
ll verify(ll n,ll m,ll s,ll k){
    ll i;
    for(i=2;i*i<=n;i++){
        if(fpow(i,fpow(n,k,s),m)!=i){
            return 0;
        }
    }
    return 1;
}
ll solve(ll n,ll m){
    ll i;
    ll s=1,h=m;
    for(i=2;i*i<=m;i+=2){
        if(m%i==0){
            m/=i;
            s*=i-1;
            p[pt++]=i;
            if(m%i==0) return -1;
        }
        if(i==2) i--;
    }
    if(m-1){
        p[pt++]=m;
        s*=m-1;
    }
    ll k=f(n,0,0);
    ll pp[50]={},ppt=0,sub=k;
    for(i=2;i*i<=sub;i+=2){
        if(sub%i==0){
            pp[ppt++]=i;
            while(sub%i==0) sub/=i;
        }
        if(i==2) i--;
    }
    if(sub-1) pp[ppt++]=sub;
    for(i=0;i<ppt;i++){
        while(k%pp[i]==0 && verify(n,h,s,k/pp[i])==1) k/=pp[i];
    }
    return k;
}
int main(){
    ll n;
    scanf("%lld",&n);
    printf("%lld",solve(n,n));
}

# 닫기