[ccJULY14] Garden Game

2014-11-02
竞赛题解 / 模拟
CodeChef

描述 Description

All bandits are afraid of Sheriff. Sheriff constantly fights crime, but when bandits lay low, he gets bored and starts to entertain himself.

This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand.

Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.

Now the Sheriff asks the question: How many times has he whistled?

输入格式 InputFormat

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the number of bandits. The second line contains N space-separated integers A1, A2, …, AN denoting that the bandit staying on position i should run to the Ai-th position after the whistle.

输出格式 OutputFormat

For each test case, output a single line containing number of times the sheriff had to whistle, print it modulo 10^9 + 7.

样例输入 SampleInput

2
3
1 2 3
5
2 3 1 5 4

样例输出 SampleOutput

1
6

CodeChef SGARDEN

代码 Code

找出每个联通块包含的个数，答案为这些值的最小公倍数。 求 Lcm 时的做法略特别，就是先算出质数表，然后求每个质数对于要求 lcm 的数可以算得的最大的幂，最后所有质数幂的积即为 lcm。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
const ll mod=1000000007;
ll i,j,t,n,m,l,r,k,z,y,x;
ll a[100005];
bool b[100005];
bool bp[100005];
vector < pair<ll,ll> > prime;
vector < pair<ll,ll> >::iterator vp;
ll T;
ll ans;
vector <ll> v;
vector <ll>::iterator vi;
inline ll find(ll s)
{
    ll i,j,t;
    t=s;
    b[t]=true;
    for (i=1;a[t]!=s;i++)
    {
        t=a[t];
        b[t]=true;
    }
    return i;
}
inline ll lcm()
{
    ll i,j,t;
    for (vi=v.begin();vi<v.end();vi++)
    {
        for (vp=prime.begin();(vp->first)<=*vi;vp++)
        {
            for (t=0;*vi%(vp->first)==0 && *vi!=0;t++)
            {
                *vi/=(vp->first);
            }
            vp->second=max(vp->second,t);
        }
    }
    t=1;
    for (vp=prime.begin();vp<prime.end();vp++) if (vp->second!=0)
    {
        for (i=1;i<=vp->second;i++) t=(t*vp->first)%mod;
    }
    return t;
}
int main()
{
    memset(bp,false,sizeof(bp)); 
    for (i=2;i<=100000;i++) if (!bp[i])
    {
        prime.push_back(make_pair(i,0));
        for (j=1;i*j<=100000;j++) bp[i*j]=true;
    }
    scanf("%lld",&T);
    while (T--)
    {
        memset(b,false,sizeof(b));
        v.clear();
        scanf("%lld",&n);
        for (i=1;i<=n;i++) scanf("%lld",&a[i]);
        for (i=1;i<=n;i++) if (!b[i]) v.push_back(find(i));
        ans=lcm()%mod;
        printf("%lld\n",ans);
        for (vp=prime.begin();vp<prime.end();vp++) vp->second=0;
    }
    return 0;
}