URAL 1456 求a模n的阶

首要条件是a,n互素，也就是求a^x=1(n)最小的x，根据欧拉函数可知最大为n的欧拉函数值。所以n的欧拉函数值的因子就可以了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
ll phi(long long n)
{
    long long rea=n;
    for(int i=2; i*i<=n; i++)
        if(n%i==0)
        {
            rea=rea-rea/i;
            do
                n/=i;
            while(n%i==0);
        }
    if(n>1)rea=rea-rea/n;
    return rea;
}
ll exp_mod(ll a,ll b,ll c)
{
    a%=c;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%c;
        b>>=1,a=a*a%c;
    }
    return ans;
}
int main()
{
    ll a,n;
    cin>>a>>n;
    if(gcd(a,n)!=1)
    {
        puts("0");
        return 0;
    }
    ll p=phi(n),l=(ll)sqrt(p*1.0),ans=1e9;
    for(ll i=1; i<=l; i++)
        if(p%i==0)
        {
            if(exp_mod(a,i,n)==1)ans=min(ans,i);
            if(exp_mod(a,p/i,n)==1)ans=min(ans,p/i);
        }
    printf("%I64d\n",ans);
    return 0;
}