hdu 4910 Problem about GCD

/*
先打表找規律，發現有兩種情況
1.當m為滿足為某個素數x的k次幂且x不為2時（或者m為偶數且m/2滿足情況也是），答案為m-1；
2.其他情況為1；
因為m很大，判定素數要用到muller_rabin随機素數判定。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;
const int S=8;
double eps=1e-8;
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}
long long f(long long x){
    long long ans=1;
    for(int i=2;i<x;i++)if(gcd(i,x)==1)ans=i*ans%x;
    return ans;
}
void text(){
    for(int i=1;i<=30;i++)
    for(int j=1;j<=30;j++)cout<<i<<"*"<<j<<" "<<f(i*j)<<endl;
    for(int i=1;i<=10;i++)cout<<(1<<i)<<" "<<f(1<<i)<<endl;
}
long long mult_mod(long long a,long long b,long long c){
    a%=c;
    b%=c;
    long long ret=0;
    long long tmp=a;
    while(b){
        if(b&1){
            ret+=tmp;
            if(ret>c)ret-=c;
        }
        tmp<<=1;
        if(tmp>c)tmp-=c;
        b>>=1;
    }
    return ret;
}
long long pow_mod(long long a,long long n,long long mod){
    long long ret=1;
    long long temp=a%mod;
    while(n){
        if(n&1)ret=mult_mod(ret,temp,mod);
        temp=mult_mod(temp,temp,mod);
        n>>=1;
    }
    return ret;
}
bool check(long long a,long long n,long long x,long long t){
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++){
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1)return true;
        last=ret;
    }
    if(ret!=1)return true;
    else return false;
}
bool muller_rabin(long long n){
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0)return false;
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    srand(time(NULL));
    for(int i=0;i<S;i++){
        long long a=rand()%(n-1)+1;
        if(check(a,n,x,t))return false;
    }
    return true;
}

long long pow2(long long x,int n){
    if(!n)return 1;
    long long res=pow2(x,n/2);
    res=res*res;
    if(n&1)res*=x;
    return res;
}

bool ok(long long m){
    if(muller_rabin(m))return 1;
    for(int i=2;;i++){
        long long x=pow(m*1.0,1.0/i)+eps;
//        cout<<m<<" "<<x<<" "<<i<<endl;
        if(pow2(x,i)==m){
            if(muller_rabin(x)){
                if(x==2)return 0;
                return 1;
            }
            if(x<=2)return 0;
        }
        if(x<2)return 0;
    }
}
void solve(long long m){
    if(ok(m))printf("%I64d\n",m-1);
    else if(m%2==0&&ok(m/2))printf("%I64d\n",m-1);
    else puts("1");
}
int main()
{
//    freopen("in","r",stdin);
//    cout<<f(47*47*2)<<endl;
//    text();
    long long m;
    while(scanf("%I64d",&m)>0&&m!=-1){
//        cout<<f(m)<<"   ";
        if(m<=5)printf("%I64d\n",m-1);//特判
        else solve(m);
    }
    return 0;
}