2015
05-23

# Double Dealing

Take a deck of n unique cards. Deal the entire deck out to k players in the usual way: the top card to player 1, the next to player 2, the kth to player k, the k+1st to player 1, and so on. Then pick up the cards �C place player 1′s cards on top, then player 2, and so on, so that player k’s cards are on the bottom. Each player’s cards are in reverse order �C 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?

There will be multiple test cases in the input. Each case will consist of a single line with two integers, n and k (1≤n≤800, 1≤k≤800). The input will end with a line with two 0s.

There will be multiple test cases in the input. Each case will consist of a single line with two integers, n and k (1≤n≤800, 1≤k≤800). The input will end with a line with two 0s.

1 3
10 3
52 4
0 0

1
4
13

http://acm.hdu.edu.cn/showproblem.php?pid=4259

Idea：

【顺便吐槽下HDU 坑爹的long long 输出，用printf("%lld",ans)一定是WA，无论G++还是C++。然后pirntf("%I64d",ans),cout<<ans;都没事。真TM坑啊，我改了一个多小时就去试出了个这】

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}

int main()
{
freopen("test.txt","r",stdin);
int N,K;
while (scanf("%d%d",&N,&K),N|| K)
{
static int rec[810][810];
static int a[810];
int num = 1;
for (int i = 1;;i++)
{
for (int j = 1;j <= K;j++)
{
rec[i][j] = num++;
if (num >N) break;
}
if (num > N) break;
}
num = 1;
for (int i = 1;i <= K;i++)
{
for (int j = (N-i)/K+1;j >= 1;j--)
{
a[num++] = rec[j][i];
}
}

static bool vd[810];
memset(vd,0,sizeof(vd));
long long ans = 1;
for (int i = 1;i <= N;i++)
{
if (vd[i]) continue;
num = i;
long long count = 0;
do
{
num = a[num];
vd[num] = true;
count++;
}
while (num != i);
ans = ans/gcd(ans,count)*count;
}
printf("%I64d\n",ans);
}

return 0;
}
/*
for (int i = 1;i <= K;i++)
{
for (int j = (N- i)/K *K + i;j > 0;j -= K)
{
a[num++] = j;
}
}
*/


Add:位置轮换的原理与实现

a[i] = j；表示的是位置i将被位置j的卡牌所替换；

i<-j <-k；如果要求i变换两次后被那个卡牌所替换，也就是求j一次变换将被哪个卡牌所替换了。当然这里的i,j,k都是第一次的初始位置编号，也可以理解成卡牌。

2）看了下其他人的程序，用的都是一步到位的方法，

for (int i = 1;i <= K;i++)

{

for (int j = (N- i)/K *K + i;j > 0;j -= K)

{ a[num++] = j; }

}