题目的描述我感觉有点问题,是看了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; }