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
思路：每个点开始，因为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 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<math.h>
6 #include<queue>
7 #include<stdlib.h>
8 #include<set>
9 #include<vector>
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 else
49 {
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 }