Let g(i) be the minimum positive integer j such that f(i, j) = i. We can show such j always exists.
For given N, A, B, find a permutation P of integers from 1 to N such that for 1 ≤ i ≤ N, g(i) equals either A or B.
更新：求的是最短的周期 f(1) = 6, f(6) = 1构成的Cycle T为A或B // 读错题系列
// f(1, j) = f(6, j-1) = p[6] = 1，此时j - 1 = 1 ==> j = 2 ==> g(1) = 2
求 Ax + By = N，x >= 0, y >= 0例1，A = 2, B = 5, N = 9，Ax + By = N ==> 2x + 5y = 9 ==> x = 2, y = 1也就是说，9个数里，有两组2个数，使得g(i) = 2。这两组数分别为2, 1和4, 3有一组5个数，使得g(i) = 5，这组数为6,7,8,9,5
A = 3, B = 6, N = 93x + 6y = 9 ==> x = 1, y = 1也就是说，9个数里，有一组3个数，使得g(i) = 3。这组数为2，3，1另有一组6个数，使得g(i) = 6。这组数为5，6，7，8，9，4
A = 4, B = 6, N = 94x + 6y = 9，无解
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3f; #define show(a) cout<<#a<<" = "<<a<<endl #define show2(b,c) cout<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl #define show3(a,b,c) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl #define show4(a,b,c,d) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<endl const int maxn = 1005; #define LOCAL int flag = false; // no exist int a, b, n, cnta, cntb; int main() { cin >> n >> a >> b; // 求 Ax + By = N，x >= 0, y >= 0 for(int i = 0; i * a <= n; i++) { int t = n - a * i; if( t%b == 0) { cnta = i; cntb = t/b; flag = true; break; } }// 求出x y int pos = 1; int lastt = pos; if( !flag ) cout << -1 << endl; else { // 构造符合条件的排列 for(int i = 1; i <= cnta; i++) { for(int k = 1; k < a; k++) cout << ++pos << ' '; cout << lastt << ' '; pos++; lastt = pos; } // 2 1 4 3 for(int i = 1; i <= cntb; i++) { for(int k = 1; k < b; k++) cout << ++pos << ' '; cout << lastt << ' '; pos++; lastt = pos; } // 6 7 8 9 5 } }