首页 > 代码库 > 福建省冬令营 Day3 T1 geronimo geronimo
福建省冬令营 Day3 T1 geronimo geronimo
题解:
将轮换拆解成置换,答案即为置换大小的最小公倍数
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 inline int Get()
9 {
10 int x = 0;
11 char c = getchar();
12 while(c < ‘0‘ || c > ‘9‘) c = getchar();
13 while(c >= ‘0‘ && c <= ‘9‘)
14 {
15 x = x * 10 + c - ‘0‘;
16 c = getchar();
17 }
18 return x;
19 }
20 const int me = 1000233;
21 int n, m;
22 int mo;
23 int tot;
24 int p[me], v[me];
25 int si[me];
26 int cou[me];
27 bool vis[me];
28 inline void Prime()
29 {
30 for(int i = 2; i <= n; ++i)
31 {
32 if(!vis[i]) p[++m] = i;
33 for(int j = 1; j <= m; ++j)
34 {
35 int c = p[j];
36 if(i * c > n) break;
37 vis[i * c] = true;
38 if(!(i % c)) break;
39 }
40 }
41 }
42 inline void Round()
43 {
44 for(int i = 1; i <= n; ++i)
45 {
46 if(vis[i]) continue;
47 ++tot;
48 int u = i;
49 while(!vis[u])
50 {
51 vis[u] = true;
52 ++si[tot];
53 u = v[u];
54 }
55 if(!si[tot]) --tot;
56 }
57 }
58 inline void Seperate()
59 {
60 for(int i = 1; i <= tot; ++i)
61 {
62 int s = 0;
63 int now = si[i];
64 while(now != 1)
65 {
66 ++s;
67 int sum = 0;
68 while(!(now % p[s])) now /= p[s], ++sum;
69 cou[s] = max(cou[s], sum);
70 }
71 }
72 }
73 inline long long Pow(int x, int y)
74 {
75 long long sum = 1;
76 while(y)
77 {
78 if(y & 1) sum = (sum * x) % mo;
79 x = (x * x) % mo;
80 y >>= 1;
81 }
82 return sum;
83 }
84 inline void Ans()
85 {
86 long long ans = 1;
87 for(int i = 1; i <= m; ++i)
88 if(cou[i])
89 ans = ans * Pow(p[i], cou[i]) % mo;
90 printf("%lld", ans);
91 }
92 int main()
93 {
94 n = Get(), mo = Get();
95 for(int i = 1; i <= n; ++i) v[i] = Get();
96 Prime();
97 for(int i = 1; i <= n; ++i) vis[i] = false;
98 Round();
99 Seperate();
100 Ans();
101 }
福建省冬令营 Day3 T1 geronimo geronimo
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。