链接:http://codeforces.com/problemset/problem/542/C
题意:对一个函数f(x),定义域[1,n], 令f(k,x) = f(f(f(f...f(x))))(共迭代k次)。求最小的k,使得f(k, x) 满足 g(g(x)) = g(x)的性质,也就是f(k,f(k,x)) = f(k,x)(x属于[1,n])。
思路:方法虽然简单,但比较巧妙,值得一做。由于f(k,x)只与f的迭代次数有关,而f数组一开始是给定的,所以不妨对所有的x属于[1,n]单独进行处理。考虑f(1,x),f(2,x),f(3,x)...,f(k,x)组成的序列,因为f(k,f(k,x)) = f(2k, x),所以转化为求序列中第k位置的数Ak,使得Ak = A2k。由于序列的后一项是前一项进行一次f()操作得到的,所以必存在循环节,且循环节长度小于等于n,不妨令序列从P0位置开始循环,循环节长度为K0,则这种情况下的k的取值集合就是{sK0, (s+1)K0, (s+2)K0, ...},sK0为大于等于P0的最小数。然后对x取遍[1,n],求k的取值集合的交集元素的最小值便是答案,但显然不能这样求。由于对自变量的每个值,k的取值总是那种情况下的循环节K0的倍数,不妨先对所有的K0求一下最小公倍数,然后再调整结果使得它满足大于等于所有的P0,调整的时候只需每次加上所有K0的最小公倍数,直到满足条件。
1 #pragma comment(linker, "/STACK:10240000,10240000") 2 3 #include <iostream> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstdlib> 7 #include <cstring> 8 #include <map> 9 #include <queue> 10 #include <deque> 11 #include <cmath> 12 #include <vector> 13 #include <ctime> 14 #include <cctype> 15 #include <set> 16 #include <bitset> 17 #include <functional> 18 #include <numeric> 19 #include <stdexcept> 20 #include <utility> 21 22 using namespace std; 23 24 #define mem0(a) memset(a, 0, sizeof(a)) 25 #define mem_1(a) memset(a, -1, sizeof(a)) 26 #define lson l, m, rt << 1 27 #define rson m + 1, r, rt << 1 | 1 28 #define define_m int m = (l + r) >> 1 29 #define rep_up0(a, b) for (int a = 0; a < (b); a++) 30 #define rep_up1(a, b) for (int a = 1; a <= (b); a++) 31 #define rep_down0(a, b) for (int a = b - 1; a >= 0; a--) 32 #define rep_down1(a, b) for (int a = b; a > 0; a--) 33 #define all(a) (a).begin(), (a).end() 34 #define lowbit(x) ((x) & (-(x))) 35 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {} 36 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 37 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 38 #define pchr(a) putchar(a) 39 #define pstr(a) printf("%s", a) 40 #define sstr(a) scanf("%s", a) 41 #define sint(a) scanf("%d", &a) 42 #define sint2(a, b) scanf("%d%d", &a, &b) 43 #define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c) 44 #define pint(a) printf("%d ", a) 45 #define test_print1(a) cout << "var1 = " << a << endl 46 #define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl 47 #define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl 48 #define mp(a, b) make_pair(a, b) 49 #define pb(a) push_back(a) 50 51 typedef long long LL; 52 typedef pair<int, int> pii; 53 typedef vector<int> vi; 54 55 const int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1}; 56 const int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1 }; 57 const int maxn = 3e4 + 7; 58 const int md = 10007; 59 const int inf = 1e9 + 7; 60 const LL inf_L = 1e18 + 7; 61 const double pi = acos(-1.0); 62 const double eps = 1e-6; 63 64 template<class T>T gcd(T a, T b){return b==0?a:gcd(b,a%b);} 65 template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;} 66 template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;} 67 template<class T>T condition(bool f, T a, T b){return f?a:b;} 68 template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];} 69 int make_id(int x, int y, int n) { return x * n + y; } 70 71 int f[207]; 72 int minv; 73 74 int find(int x) { 75 int used[207], c = 0; 76 mem0(used); 77 while (!used[f[x]]) { 78 c ++; 79 used[x = f[x]] = c; 80 } 81 max_update(minv, used[f[x]]); 82 return c - used[f[x]] + 1; 83 } 84 85 int main() { 86 //freopen("in.txt", "r", stdin); 87 int n; 88 cin >> n; 89 rep_up1(i, n) { 90 sint(f[i]); 91 } 92 LL ans = 1; 93 rep_up1(i, n) { 94 LL tmp = find(i); 95 ans = ans / gcd(ans, tmp) * tmp; 96 } 97 LL tmp = ans; 98 while (ans < minv) ans += tmp; 99 cout << ans << endl; 100 return 0; 101 }