- home
- Competitions
- Topcoder SRM 652 Div1 Easy: ThePermutationGame
Topcoder SRM 652
Div1 Easy: ThePermutationGame
問題
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 の最小公倍数を求めれば良い. 各素因数の最大指数を取り出していく.
解答
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
}; |