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 思路:每个点开始,因为x->y,y->x,那么这必定是一个环,所以就先找到环,然后假设环上不同的两点,相距x1,L-x1; 那么从一点开始到达另一点走x1+k1*L,那么另一点就为L - x1 + k2*L ; 这两个要相同,那么有X%L = x1&&X%L = L-x1;所以当L为偶数时最小为X=L/2;否则为X=L; 最后每个环求最小公倍数。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 typedef long long LL;11 using namespace std;12 int ans[1005];13 LL cnt[1000005];14 int ma[105];15 bool flag[105];16 LL gcd(LL n,LL m);17 int main(void)18 {19 int n;20 scanf("%d",&n);21 int i,j;22 for(i = 1; i <= n; i++)23 {24 scanf("%d",&ans[i]);25 }26 memset(ma,-1,sizeof(ma));27 int id = -1;28 for(i = 1; i <= n; i++)29 {30 int t = 0;31 memset(flag,0,sizeof(flag));32 int v = ans[i];33 while(!flag[v])34 {35 t++;36 flag[v] = true;37 cnt[v] = t;38 v=ans[v];39 if(v == i)40 {t++;ma[i] = t;break;}41 }42 }43 int fl = 0;LL ak = 1;44 for(i = 1; i <=n; i++)45 {46 if(ma[i]==-1)47 fl = 1;48 else49 {50 if(ma[i]%2==0)51 ma[i]/=2;52 LL ac = gcd(ma[i],ak);53 ak = ak/ac*ma[i];54 }55 }56 if(fl)printf("-1\n");57 else printf("%lld\n",ak);58 return 0;59 }60 LL gcd(LL n,LL m)61 {62 if(m == 0)63 return n;64 else return gcd(m,n%m);65 }