hdu 5392 许多数的lcm的取模

2019-04-14 16:49发布

站内文章 / 模拟电子
9369 0 1092
算出每个循环块的长度，直接相乘肯定是不行的，需要分解质因数，每个因子取每次分解出来数量的最大值，然后用下快速幂优化下乘法就好了，比赛时脑子短路了，一直wa #include #include #include using namespace std; const int N=3e6+10; const long long MOD=3221225473; int n; int a[N]; bool vis[N]; int b[N],ma; long long res=1; void rd(int&x){ char ch; for(ch=getchar();ch<'0' || ch>'9';ch=getchar()); x=0; for(;ch>='0' && ch<='9';ch=getchar()) x=x*10+ch-'0'; } long long solve(long long x,long long y){ long long res=1; while(y){ if(y&1) res=(res*x)%MOD; x=(x*x)%MOD; y>>=1; } return res; } int main(){ #ifndef ONLINE_JUDGE freopen("aaa","r",stdin); #endif int T; scanf("%d",&T); while(T--){ scanf("%d",&n); ma=-1; for(int i=1;i<=n;i++){ rd(a[i]);ma=max(ma,a[i]);} memset(vis,0,sizeof vis); memset(b,0,sizeof b); bool find=false; for(int i=1;i<=n;i++){ if(vis[i] || a[i]==i) continue; int j=i,cnt=0; find=true; while(!vis[j]){cnt++;vis[j]=true;j=a[j];} int tmp=cnt; for(int i=2;i*i<=tmp;i++){ if(cnt%i==0){int num=0;while(cnt%i==0){cnt/=i;num++;}b[i]=max(b[i],num);} if(cnt==1) break; } if(cnt>1) b[cnt]=max(b[cnt],1); } res=1; if(!find){puts("0");continue;} for(int i=2;i<=ma;i++) if(b[i])res=(res*solve(i,b[i]))%MOD; cout<

热门文章