循环（NOIP2005普及组第四题）

本文主要是介绍循环（NOIP2005普及组第四题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

循环(circle.pas/circle.in/circle.out)

（NOIP2005普及组T4）
（LYOI20090321信息学综合模拟Problem2）

问题描述
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
2 2486 4
3 3971 4
4 46 2
5 5 1
6 6 1
7 7931 4
8 8426 4
9 91 2
这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？
注意：
1．如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2．如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。

样例输入
32 2
样例输出
4
数据规模
对于30%的数据，k <= 4；
对于全部的数据，k <= 100
思路：
这个题我之前是在OJ上做过的，也知道这是NOIP题目，但是一直是0分没有AC。今天终于AC啦。下面讲讲思路：
一开始我的思路就已经有点沾正解的边了，一开始我是认为对于最终的结果SOLVE(N,K)，这个数一定是N的最后一位的循环节的倍数，比如说：SOLVE(1234567,7)一定是7的循环节，也就是4的倍数。然后就可以每1234567^4进行一次乘法，不考虑精度的话，本以为这样就能得出30%的答案了，但是只得了2个点。
这里我们记X的循环节为FUNC(X)，经过半个下午的思考，发现其实自己只需要把刚才的思路再拓展一下就好了。
比如说以SOLVE(223,3)为例，此时T=FUNC(3)=4模拟一下就是
223^1≡223(mod 1000)
223^2≡729(mod 1000)
223^3≡567(mod 1000)
223^4≡441(mod 1000)
先让它的倍增单位变为[223^FUNC(3)]%（10^3）=441，也就是每次都乘上441，然后就能保证个位每次都是3，记录循环节4，解释一下就是：
223*(441^1)≡343(mod 1000)
223*(441^2)≡263(mod 1000)
223*(441^3)≡983(mod 1000)
223*(441^4)≡503(mod 1000)
223*(441^5)≡823(mod 1000)
这个时候发现，223的十位为2，823的十位也为2，这样每次倍增单位就变成了(441^5)mod 1000=201，然后就能保证十位每次都是2，个位每次都是3。记录循环4*5=20
223*(201^1)≡823(mod 1000)
223*(201^2)≡423(mod 1000)
223*(201^3)≡023(mod 1000)
223*(201^4)≡623(mod 1000)
223*(201^5)≡223(mod 1000)
这个时候发现，223的百位为2，求出的223的百位也为2，这时得到的数已经到了K位了。然后就能保证百位每次都是2，十位每次都是2，个位每次都是3。记录循环4*5*5=100。
然后输出即可。
通过模拟可能思路就比较明晰了。
过程中要用到一个高精乘高精和一个高精乘低精，然后个人认为没必要为了省这点时间去打长长的高精度快速幂。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<set>
using namespace std;
int a[201],k,i,j,t[201];
int shl[10]={1,1,4,4,2,1,1,4,4,2};
string s;
int last[201];
int n[201],ans[201],aans[201],now[201];
int r()
{int ans=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){ans*=10;ans+=ch-'0';ch=getchar();}return ans*f;
}void multiply(int x[],int y[],int z[])
{int up=0;//进位 for(int ii=1;ii<=k;ii++){for(j=1;j<=k;j++){z[ii+j-1]+=(x[j]*y[ii]+up)%10;up=(x[j]*y[ii]+up)/10;}up=0;}for(int ii=1;ii<=k;ii++){z[ii+1]+=z[ii]/10;z[ii]%=10;}
}void multiply1(int x[],int yy,int z[])
{int up=0;//进位 for(int ii=1;ii<=k;ii++){z[ii]=(x[ii]*yy+up)%10;up=(x[ii]*yy+up)/10;}
}int main()
{
//  freopen("circle.in","r",stdin);
//  freopen("circle.out","w",stdout);cin>>s;k=r();int temp=0,len=s.size();for(i=len-1;i>=len-k;i--)n[++temp]=s[i]-'0';for(i=1;i<=k;i++)ans[i]=n[i];for(i=1;i<shl[n[1]];i++){memset(aans,0,sizeof(aans));multiply(ans,n,aans);for(j=1;j<=k;j++){ans[j]=aans[j];}}t[1]=shl[n[1]];for(j=1;j<=k;j++)now[j]=ans[j];int pos=2;while(pos<=k){for(j=1;j<=k;j++)ans[j]=n[j],last[j]=now[j];temp=0;while(temp<11){temp++;memset(aans,0,sizeof(aans));multiply(ans,now,aans);for(j=1;j<=k;j++)ans[j]=aans[j];if(ans[pos]==n[pos])break;memset(aans,0,sizeof(aans));multiply(last,now,aans);for(j=1;j<=k;j++)last[j]=aans[j];}if(temp>=11){cout<<-1;return 0;}for(j=1;j<=k;j++)now[j]=last[j];memset(aans,0,sizeof(aans));multiply1(t,temp,aans);for(j=1;j<=100;j++)t[j]=aans[j];pos++;}int kk=0;for(i=100;i>=1;i--){if(t[i])kk=1;if(kk)cout<<t[i];}return 0;
}