BZOJ 2613 Poi2003 Shuffle 数论

题目大意：给定一个长度为 n 的置换 b 和一个正整数 k ， 求一个置换 a ，使得 ak=b

要做这个题首先我们需要知道 ak 是什么
想象一个长度为 L 的循环，如果我们将这个循环求 k 次方，我们将会得到 Gcd(L,k) 个长度为 LGcd(L,k) 的循环
那么现在我们将 b 分解成循环，假如现在我们得到了一个长度为 L′ 的循环，那么由之前的结论可以得到 L′=LGcd(L,k)
容易证明存在一个最小的 L 满足这个 L 是所有合法的 L 的约数，且这个 L 满足对于 L′ 的任意一个质因子 p ， p 在 L 中的次数等于 p 在 L′ 中的次数加上 p 在 k 中的次数

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define M 1001001 using namespace std; int n,k; int a[M],ans[M]; bool v[M]; vector
        
          *stack[M];int top; bool Compare(vector
         
           *v1,vector
          
            *v2) { return v1->size() < v2->size() ; } void Get_Circulation(int x,vector
           
             *vec) { while(1) { if(v[x]) return ; vec->push_back(x); v[x]=true;x=a[x]; } } int Get_L(int x) { int i,k=::k,re=1; for(i=2;i*i<=x;i++) if(x%i==0) { while(x%i==0) x/=i,re*=i; while(k%i==0) k/=i,re*=i; } if(x!=1) { re*=x; while(k%x==0) k/=x,re*=x; } return re; } int main() { int i,j,k; cin>>n>>::k; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) if(!v[i]) Get_Circulation(i,stack[++top]=new vector
            
             ); sort(stack+1,stack+top+1,Compare); for(i=1;i<=top;) { static int a[M]; int L=Get_L(stack[i]->size()); int temp=__gcd(L,::k); for(j=0;j
             
              size();k++) a[(j+(long long)k*::k)%L]=(*stack[i+j])[k]; for(j=0;j