Arpa's loud Owf and Mehrdad's evil plan
1 second
256 megabytes
standard input
standard output
As you have noticed, there are lovely girls in Arpa’s land.
People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.
Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.
The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.
Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.
Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i).
The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.
The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.
If there is no t satisfying the condition, print -1. Otherwise print such smallest t.
4
2 3 1 4
3
4
4 4 4 4
-1
4
2 1 4 3
1
In the first sample suppose t = 3.
If the first person starts some round:
The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.
The process is similar for the second and the third person.
If the fourth person starts some round:
The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.
In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.
【分析】题目扯了一大堆，主要是这个意思。n个人，每个人有一个打电话的对象（可以是自己），设t为打电话的总次数，当一个人打电话时，他只打给自己的对象，然后他的对象接着打给自己的对象。。。问最小的t，使得从任意的x开始打电话，总共打了t次后到达y，这一轮结束，然后y接着打，总共打了t次后又回到x,(x与y可等)。
说白了，就是一个有向图，找遍所有的环，若环为偶数，则/2，求所有的最小公倍数。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 10000000000000
#define met(a,b) memset(a,b,sizeof a)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
using namespace std;
const int N = 1e2+;
const int M = 4e5+;
int dp[N][];
int n,sum[N],m=,p,k;
int Tree[N];
ll w[N][N],vis[N];
void Floyd(){
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(w[i][k]!=inf&&w[k][j]!=inf&&w[i][j]>w[i][k]+w[k][j]){
w[i][j]=w[i][k]+w[k][j];
}
}
}
}return;
}
int GCD(int minn,int maxn){
if(maxn%minn==)return minn;
else return GCD(min(minn,maxn%minn),max(minn,maxn%minn));
}
int main()
{
for(int i=;i<N;i++)for(int j=;j<N;j++)w[i][j]=inf;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&k);
w[i][k]=;
}
Floyd();
ll ans=inf;
bool flag=false;
for(int i=;i<=n;i++){
if(w[i][i]<inf){
if(w[i][i]&){
if(!flag)ans=w[i][i],flag=true;
else ans=(ll)ans*(w[i][i]/GCD(min(w[i][i],ans),max(w[i][i],ans)));
}
else {
w[i][i]/=;
if(!flag)ans=w[i][i],flag=true;
else ans=(ll)ans*(w[i][i]/GCD(min(w[i][i],ans),max(w[i][i],ans)));
}
}
else if(w[i][i]==inf){
ans=inf;
break;
}
}
if(ans==inf)puts("-1");
else printf("%lld\n",ans);
return ;
}