首页 > 代码库 > HDOJ 4259 Double Dealing
HDOJ 4259 Double Dealing
找每一位的循环节,求lcm
Double Dealing
Time Limit: 50000/20000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1806 Accepted Submission(s): 622
Problem Description
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 – 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 – 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?
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, n and k (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 3 10 3 52 4 0 0
Sample Output
1 4 13
Source
The University of Chicago Invitational Programming Contest 2012
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; int n,m; typedef long long int LL; int next[880],to[880]; bool vis[880]; LL gcd(LL a,LL b) { if(b==0) return a; return gcd(b,a%b); } LL lcm(LL a,LL b) { return a/gcd(a,b)*b; } int get_int() { char ch; int ret=0; while(ch=getchar()) { if(ch>='0'&&ch<='9') { ret=ret*10+ch-'0'; } else break; } return ret; } int main() { while(true) { n=get_int();m=get_int(); if(n==0&&m==0) break; if(n<=m) { puts("1"); continue; } ///mo ni yi chi for(int i=1;i<=n;i++) next[i]=i; for(int i=1;i<=m;i++) { to[i]=n/m; if(i<=n%m) to[i]++; to[i]+=to[i-1]; } for(int i=1;i<=n;i++) { next[i]=to[(i-1)%m+1]--; } LL ans=1; memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) { if(vis[i]) continue; int t=next[i]; LL temp=1; while(t!=i) { vis[t]=true; t=next[t]; temp++; } ans=lcm(ans,temp); } printf("%I64d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。