問題

http://community.topcoder.com/stat?c=problem_statement&pm=13229&rd=16316

整数 N (< 100,000) が与えられる. 1 ~ N の置換 (1 ~ N を並び替えた配列) P を考える. 置換 P を m 回適用した結果を f(m) とする. f(1) = P(1), f(2) = P(P(1)), …

長さ N の任意の置換について, f(x) = 1 となるような最小の x を求めよ. 答えを 1,000,000,007 の剰余で出力せよ.

解法

1 ~ N の最小公倍数を求めれば良い. 各素因数の最大指数を取り出していく.

解答

#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
class ThePermutationGame
{
public:
int findMin (int N)
{
int p[100010] = {};
for (int n = 1; n <= N; n++) {
int m = n;
for (int i = 2; i * i <= m; i++) {
int cnt = 0;
while (m % i == 0) {
m /= i;
cnt++;
}
p[i] = max(p[i], cnt);
}
if (m > 1) p[m] = max(p[m], 1);
}
ll ans = 1;
for (int n = 1; n <= N; n++) {
loop (p[n], i) {
ans = (ans * n) % MOD;
}
}
return ans;
}
};
view raw gistfile1.cpp hosted with ❤ by GitHub