ZOJ 2964 Triangle (非常好的一个数论题)

ZOJ 2964 Triangle

题目的描述我感觉有点问题,是看了shi哥空间才知道的.三角形的三边l>m>n,a^l=a^m=a^n(modz),由于三边不等,所以说要使边权和最小,就要找到a生成的子群规模.由于我们知道他肯定是euler(z)的约数,所以枚举约数进行寻找,这个题就亮在这个寻找约数的过程.

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long  LL;
LL euler(int n)
{
    LL i,m,temp = n;
    m = (LL)sqrt( (double)n + 0.5 );
    for( i = 2; i <= m; i++ )
        if( n%i == 0)
        {
            temp = temp/i*(i-1);
            while(n%i ==0) n/=i;
        }
    if( n > 1 ) temp = temp/n*(n-1);
    return temp;
}
LL f(LL a,LL k,LL M){
    LL b = 1;
    while( k ){
        if( k&1 )
            b = (a%M)*(b%M)%M;
        a = (a%M)*(a%M)%M;
        k /= 2;
    }
    return b;
}

int main(void)
{
	LL eu,out,i,cases,a,z;
	cin>>cases;
	while( cases-- )
	{
		cin>>a>>z;
		if( z==1 || a==1 )
		{cout<<9<<endl;continue;}
		eu = euler(z);
		for(i = 1; i *i <= eu; i++ )
		{
			if( eu%i == 0 )
			{
				if( f(a,i,z)==1 ) 
				{out=i;break;}
				else if( f(a,eu/i,z)==1 )
				out = eu/i;
			}
		}
		cout << 6*out+3 << endl;
	}
	return 0;
}