题意：一个置换群，经过最少k次置换后还原。问给一个N个元素，在所有的置换群里，有多少个不同的k。
分析：这道题可以转化成：N = Σ ai ，求LCM ( ai )有多少个不同的值。比如N=10时，k可为：1，2，3，2*2，5，2*3，7，2*2*2，3*3，2*5，2*2*3，2*7，3*5，2*2*5，3*7，2*3*5，共16个，这里用到了唯一分解定理：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如: 
。那么先预处理出1000内的素数，dp[i][j]表示用到了前i个素数，组成和为j，的个数，一个素数可能用到多次。因为1对结果不影响，所以结果是Σ dp[m][i] (m最大的素数<=n，i<=n)
收获：1. 置换群和唯一分解定理 2. DP和数论结合
代码：
/************************************************
* Author :Running_Time
* Created Time :2015-8-27 18:11:40
* File Name :F.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int prime[N/2];
bool is_prime[N];
ll dp[200][N]; int seive(void) {
int p = 0;
memset (is_prime, true, sizeof (is_prime));
for (int i=2; i<=1000; ++i) {
if (is_prime[i]) prime[++p] = i;
for (int j=1; j<=p && prime[j]*i<=1000; ++j) {
is_prime[i*prime[j]] = false;
if (i % prime[j] == 0) break;
}
}
return p;
} int main(void) {
int p = seive ();
int n, m = 0;
while (scanf ("%d", &n) == 1) {
memset (dp, 0, sizeof (dp));
dp[0][0] = 1;
for (int i=1; i<=p; ++i) {
for (int j=0; j<=n; ++j) dp[i][j] = dp[i-1][j];
int res = prime[i];
if (res <= n) m = i;
else break;
while (res <= n) {
for (int j=0; j+res<=n; ++j) {
if (dp[i-1][j]) dp[i][j+res] += dp[i-1][j];
}
res *= prime[i];
}
}
ll ans = 0;
for (int i=1; i<=n; ++i) ans += dp[m][i];
printf ("%I64d\n", ans + 1);
} return 0;
}