POJ3590TheshuffleProblem置换+DP

题意&＃xff1a;对每一个置换T&＃xff0c;都存在一个T^k &＃61; e。现在让你求一个n元置换&＃xff0c;使得它的阶最大&＃xff0c;即当T^k &＃61; e时&＃xff0c;k最大。若同时存在多个这样的T&＃xff0c;那么输出其中排序最小的。

题解&＃xff1a;由于每一个置换都可以分解成若干个轮换&＃xff0c;那么这些轮换的阶的最小公倍数就是该置换的阶。

所以题目可以变成这样&＃xff1a;给你一个整数n&＃xff0c;求n1&＃43;n2&＃43;n3&＃96;&＃96;&＃96;&＃43;ni &＃61; n。 并且n1,n2,&＃96;&＃96;&＃96;ni的最小公倍数最大。

1.求最小公倍数并不难&＃xff0c;动态规划解决。

2.那么求得最小公倍数之后怎么保证置换排序最小呢&＃xff1f;

我们不妨令某个最小公倍数为lcmMax&＃xff0c; 那么将lcmMax因式分解之后得到 lcmMax &＃61; p1^k1*p2^k2*&＃96;&＃96;pi^ki 

并且p1^k1&＃43;p2^k2&＃43;···&＃43;pi^ki <&＃61; n。这个是显然的&＃xff0c;因为 lcmMax &＃61; p1^k1*p2^k2*&＃96;&＃96;pi^ki <&＃61; n1*n2*n3&＃96;&＃96;&＃96;*ni

而n1&＃43;n2&＃43;n3&＃96;&＃96;&＃96;&＃43;ni &＃61; n&＃xff0c;所以p1^k1&＃43;p2^k2&＃43;···&＃43;pi^ki <&＃61; n。

3.用次用pi^ki个元素构成一个轮换&＃xff0c;那么就能保证该置换T的阶最大。

那么你可能会问&＃xff0c;剩下的元素怎么办呢&＃xff1f;其实全部让它们为一阶轮换就OK了&＃xff0c;因为一阶轮换并不影响最后T的阶。

#include
#include
#include
using namespace std;#define N 110
#define lint __int64
lint dp[N][N], maxLcm[N];
lint factor[N], fnum;
int p[25] &＃61;{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};inline lint gcd ( lint a, lint b )
{lint c;while ( b !&＃61; 0 ){c &＃61; a % b;a &＃61; b;b &＃61; c;}return a;
}void split ( int n )
{int i, j, k, lcm;memset(dp,0,sizeof(dp));for ( i &＃61; 1; i <&＃61; n; i&＃43;&＃43; )dp[i][1] &＃61; i;for ( i &＃61; 2; i <&＃61; n; i&＃43;&＃43; )for ( j &＃61; 2; j <&＃61; i; j&＃43;&＃43; )for ( k &＃61; 1; k &＃61; j-1; k&＃43;&＃43; ){lcm &＃61; dp[i-k][j-1] * k / gcd(dp[i-k][j-1], k);if ( lcm > dp[i][j] ) dp[i][j] &＃61; lcm;}for ( i &＃61; 1; i <&＃61; n; i&＃43;&＃43; ){maxLcm[i] &＃61; 0;for ( j &＃61; 1; j <&＃61; n; j&＃43;&＃43; )if ( dp[i][j] >&＃61; maxLcm[i] )maxLcm[i] &＃61; dp[i][j];}
}void split ( lint num )
{fnum &＃61; 0;for ( int i &＃61; 0; i <25; i&＃43;&＃43; ){if ( num % p[i] ) continue;factor[fnum] &＃61; 1;while ( num % p[i] &＃61;&＃61; 0 ){factor[fnum] *&＃61; p[i];num /&＃61; p[i];}fnum&＃43;&＃43;;}
}int main()
{int t, n;split(100);scanf("%d",&t);while ( t-- ){scanf("%d",&n);split ( maxLcm[n] );sort(factor,factor&＃43;fnum);int i, j, k, tmp &＃61; 0;for ( i &＃61; 0; i }