hdu4259 Double Dealing----置换群

Double DealingTime Limit: 50000/20000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 290 Accepted Submission(s): 132


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>#define ll __int64using namespace std;int n,k;int a[810][810];bool f[810];int num[810];ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b);}int main(){ while(scanf("%d%d",&n,&k)!=EOF) { if(n==0&&k==0) break; if(n<k){puts("1"); continue;} int oo=1; for(int i = 1; i <= k && i <= n; i++) for(int j = (n - i) / k * k + i; j > 0; j -= k) num[oo++] = j; int x; ll res=1; memset(f,false,sizeof(f)); for(int i=1;i<=n;i++) { x=i; if(f[i]) continue; int count=0; while(1) { f[x]=true; x=num[x]; count++; if(x==i) break; } res=res/gcd(res,count)*count; } cout<<res<<endl; }}