首页 > 代码库 > HDU 4259
HDU 4259
虽然知道是置换，却很久没有思路。忽然想到，由初始状态A经过变换后回到A状态，应该是不停循环可重复的。于是，猜想数字的位置也是重复循环的。拿了个例子验证了一下，某然是这样。例如第二个10，3的例子有1-》4-》3-》10-》1.
于是，可以按照上题的方法求解了。
#include <iostream>#include <algorithm>#include <cstdio>#define LL __int64#define N 800using namespace std;int num[N+1];bool vis[N+1];int stack[N+1],top;LL gcd(LL a,LL b){ if(b==0) return a; return gcd(b,a%b);}int main(){ int n,k; while(scanf("%d%d",&n,&k),n||k){ if(n<=k){ printf("1\n"); continue; } memset(vis,false,sizeof(vis)); int counted=0; for(int i=1;i<=n;i++){ //此处是可以优化的，可以通过计算来做。 if(!vis[i]){ int tmp=i; top=0; while(tmp<=n){ vis[tmp]=true; stack[++top]=tmp; tmp+=k; } while(top>0){ num[++counted]=stack[top]; top--; } } } memset(vis,false,sizeof(vis)); top=0; for(int i=1;i<=n;i++){ if(!vis[i]){ int k=i; counted=0; while(!vis[k]){ vis[k]=true; k=num[k]; counted++; } stack[++top]=counted; } } LL ans=(LL)stack[top--]; for(int i=top;i>0;i--){ ans=ans*((LL)stack[i]/gcd(ans,(LL)stack[i])); } printf("%I64d\n",ans); } return 0;}
HDU 4259
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。