最长的循环节

基准时间限制：1 秒 空间限制：131072 KB
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1035

题目：

正整数k的倒数1/k，写为10进制的小数如果为无限循环小数，则存在一个循环节，求<=n的数中，倒数循环节长度最长的那个数，假如存在多个最优的答案，输出所有答案中最大的那个数。

1/6= 0.1(6) 循环节长度为1
1/7= 0.(142857) 循环节长度为6
1/9= 0.(1) 循环节长度为1

Input：

输入n（10≤n≤1000)n（10 \leq n \leq 1000)

Output:

输出<=n的数中倒数循环节长度最长的那个数

sample:

input:

10

Output:

7

题解：

这题涉及一个神奇的数学证明，接下来我们证明看看：
首先我们用一个假设一个循环小数看看。
k=ba=0.0......⏟s位(c1c2...cr)⏟r位k=\frac{b}{a}=0.0\underbrace{......}_{s位}\underbrace{(c_1c_2...c_r)}_{r位}
可以看到kk是一位循环位数为rr的循环小数，现在我们把小数点右rr位。由于kk是rr位循环小数，所以小数部分只有前s位改变。当我们把这个数的小数部分与kk的小数部分相减后，小数部分就只剩最多s位了。这是的数可以表示成
k1=(10r−1)∗(b/a)k_1=(10^r-1)*(b/a)
我们再右移ss位，这时候就变成了
k2=10s∗(10r−1)∗(b/a)k_2=10^s*(10^r-1)*(b/a)
因为bb与aa互质，1010与aa互质，所以要k2k_2为整数只有(10r−1) mod a=0(10^r-1)\,mod\,a=0.因此有
10r≡1(mod a)10^r\equiv1(mod\,a)
得出这个公式之后，我们只要每一个数如果它和10互质，就找出最小的满足公式的rr即可(说白了就是求10关于模a的阶)，不过值得注意的是，根据欧拉定理10Φ(a)≡1(mod a)10^{\Phi(a)}\equiv1(mod\, a)，r一定是Φ(a)\Phi(a)的因子，这样就更容易求了。
实在看不懂可以看下这个：
http://w3.math.sinica.edu.tw/math_media/d253/25311.pdf

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int phi[maxn];
void Phi()//欧拉筛
{
	memset(phi,0,sizeof(phi));
	phi[1]=1;
	for(int i=2;i<=maxn;i++)
	{
		if(!phi[i])
		{
			for(int j=i;j<=maxn;j+=i)
			{
				if(!phi[j])
					phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
//		cout<<i<<" "<<phi[i]<<endl;
	}
}
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
int qpow(int a,int b,int mod)//快速幂
{
	long long ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	int T,n,i,j,k,temp,ans;
	Phi();
	long long sum;
	cin>>n;
	int _max=-1;
	for(i=2;i<=n;i++)
	{
		temp=gcd(i,10);
		if(temp!=1)
			continue;
		for(j=1;j<=phi[i];j++)
		{
			if(phi[i]%j==0&&qpow(10,j,i)==1)
			{
				if(j>_max)
				{
					_max=j;
					ans=i;
				}
//				cout<<i<<" "<<j<<endl;
				break;
			}
		}
	}
	cout<<ans<<endl;
}

Q.E.D.