BZOJ 2613 Poi2003 Shuffle 數論

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中的次數
於是我們找到這個最小的L，將LGcd(L,k)個長度為L′的循環合並成一個循環即可
BZ上沒有SPJ，建議去main上交
回頭寫個SPJ去

#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;jsize();k++)
                a[(j+(long long)k*::k)%L]=(*stack[i+j])[k];
        for(j=0;j