首页 > 代码库 > HDU 4259 Double Dealing【简单群置换】
HDU 4259 Double Dealing【简单群置换】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4259
题目大意:给出n张卡片以及k个人,现在对卡片进行分堆,然后分发(这样卡片改变了顺序),依次这样问多少次后卡片顺序回到原来一样。
比如给出的10,3.
第一次分堆是这样的
第一人:1,4,7,10
第二人:2,5,8
第三人:3,6,9
其顺序由1 2 3 4 5 6 7 8 9 10 变成了 10 7 4 1 8 5 2 9 6 3
即:
10 3 第一次 10 7 4 1 8 5 2 9 6 3 第二次 3 2 1 10 9 8 7 6 5 4 第三次 4 7 10 3 6 9 2 5 8 1 第四次 1 2 3 4 5 6 7 8 9 10在第四次可以回到原来的顺序。
其循环节是:
位置的变化有如下规律:
1->4->3->10->1; 循环节是4
2->7->2; 循环节是2
5->6->9->8->5; 循环节是4
其最大的公约数是4.
故其答案是4.
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #define LL long long using namespace std; int a[1000], vis[1000]; LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } int main() { int i,j,n,k,t; while(~scanf("%d%d",&n,&k)){ LL ans,sum=1; if(n==0&&k==0) break; t=0; for(i=0; i<k&&i<n; i++) for(j=(n-i-1)/k*k+i; j>=0; j-=k) a[t++]=j; for(int i=0;i<=n;i++) cout<<a[i]<<endl; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++){ int x=i; ans=0; while(!vis[x]){ ans++; vis[x]=1; x=a[x]; } if(ans) sum=sum/gcd(sum,ans)*ans; } printf("%I64d\n",sum); } }
HDU 4259 Double Dealing【简单群置换】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。