1024.cpp

来自「我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2」· C++ 代码 · 共 49 行

#include <iostream>
using namespace std;

const int maxN = 1000;
int a[maxN + 1], len[ maxN + 1 ];
bool visit[maxN + 1];
int gcd(int a, int b)
{
    while( b != 0 )
    { int c = a%b; a = b; b = c; }
    return a; 
}

int gbs(int a,int b)   //lcm least common multiple
{
    int c = gcd(a, b);
    return a/c*b;
}
int main()
{
    int i,n,t;
    memset( visit ,false ,sizeof( visit ) );
    
    cin >> n;
    for( i = 1; i <= n; i++ )
         cin >> a[i];
    for( i = 1; i <= n; i++ )
    {
         int c = 0;
         t = i;
         if ( !visit[i] ) do {
            t = a[t];
            c++;
            visit[t] = true;
          }
         while( t != i );
         
         len[i] = c;
    }
    
    int ans = 1;
    for( i  =1; i <= n; i++)
    {
         if(len[i] != 0 )ans = ( gbs( ans, len[i] ) );
    }
    cout << ans << endl;
    return 0;
}