最长的循环节
基准时间限制: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:
输入
Output:
输出<=n的数中倒数循环节长度最长的那个数
sample:
input:
10
Output:
7
题解:
这题涉及一个神奇的数学证明,接下来我们证明看看:
首先我们用一个假设一个循环小数看看。
可以看到是一位循环位数为的循环小数,现在我们把小数点右位。由于是位循环小数,所以小数部分只有前s位改变。当我们把这个数的小数部分与的小数部分相减后,小数部分就只剩最多s位了。这是的数可以表示成
我们再右移位,这时候就变成了
因为与互质,与互质,所以要为整数只有.因此有
得出这个公式之后,我们只要每一个数如果它和10互质,就找出最小的满足公式的即可(说白了就是求10关于模a的阶),不过值得注意的是,根据欧拉定理,r一定是的因子,这样就更容易求了。
实在看不懂可以看下这个:
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.