题目链接：?pid=4259
Problem Description
Take a deck ofnunique cards. Deal the entire deck out tokplayers in the usual way: the top card to player 1, the next to player 2, thekthto playerk, thek+1stto player 1, and so on. Then pick up the cards – place player 1′s cards on top, then player 2, and so on, so that playerk’s cards are on the bottom. Each player’s cards are in reverse order – the last card that they were dealt is on the top, and the first on the bottom.How many times, including the first, must this process be repeated before the deck is back in its original order?
Input
There will be multiple test cases in the input. Each case will consist of a single line with two integers,nandk(1≤n≤800, 1≤k≤800). The input will end with a line with two 0s.
Output
For each test case in the input, print a single integer, indicating the number of deals required to return the deck to its original order. Output each integer on its own line, with no extra spaces, and no blank lines between answers. All possible inputs yield answers which will fit in a signed 64-bit integer.
Sample Input
1 310 352 40 0
Sample Output
1413
Source
The University of Chicago Invitational Programming Contest 2012
题意：给出 n 张卡片， 分给k个人， 从 1 – n 轮流分。
然后，重新把卡片放在一起。第1个人的卡片放在最上边，后面的依次放下面。
再重新分，再放，直到最后变成初始的顺序；
求一共换了多少次！
PS:
朴素思想：模拟对每个点进行变换，分别求得周期Ci，然后求他们的最小公倍数。（TLE）
优化：可以得知当某个位置上的卡牌由A变回到A是，，会经历一个A->B->C->…->A的密闭循环，
这样对于循环内的每个元素，只需要计算其中任一元素即可。
代码如下：
#include <cstdio>#include <cstring>#define maxn 847#define LL __int64int a[maxn][maxn], b[maxn];LL GCD(LL a, LL b){if(b == 0)return a;return GCD(b,a%b);}int main(){int n, k;int vis[maxn];while(~scanf("%d%d",&n,&k)){if(n==0 && k==0)break;memset(vis, 0,sizeof(vis));int cnt = 1;int i;for(i = 0; ; i++){for(int j = 0; j < k; j++){a[i][j] = cnt++;}if(cnt > n)break;}cnt = 1;for(int j = 0; j < k; j++){for(int h = i; h >= 0; h–){if(a[h][j] && a[h][j] <= n)b[cnt++] = a[h][j];}}LL ans = 1, cont;for(int i = 1; i <= n; i++){if(!vis[i]){cont = 0;int t = i;while(1){if(vis[t])break;vis[t] = 1;t = b[t];cont++;}ans = ans/GCD(ans,cont)*cont;//最小公倍数}}printf("%I64d\n",ans);}return 0;}
我们大都接受的是正面的教育，
