转自：

https://blog.csdn.net/define_danmu_primer/article/details/52456763

51nod 1035 最长的循环节(无限小数的循环节)

2016年09月07日 09:53:13 单木阅读数：867更多

定理

如果1<=b<a1<=b<a,a没有2或5的质因子，并且a与b互质，那么b/ab/a 的循环节位数恰好等于min(10e≡1(moda))min(10e≡1(moda)),e是正整数。
如果1<=b<a1<=b<a,a没有2或5的质因子，并且a与b互质，那么b/ab/a 的循环节位数必整除ϕ(a)ϕ(a)。

代码

/* ********************************

Author : danmu

Created Time : 2016年09月07日星期三 09时01分10秒

File Name : a.cpp

******************************** */

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <string>

#include <vector>

#include <cstdio>

#include <stack>

#include <queue>

#include <cmath>

#include <list>

#include <map>

#include <set>

#define rep(i,x,y) for(int i=x;i<=y;++i)

#define _rep(i,x,y) for(int i=x;i>=y;--i)

#define CL(S,x) memset(S,x,sizeof(S))

#define CP (S1,S2) memcpy(S1,S2,sizeof(S2))

#define ALL(x,S) for(x=S.begin();x!=S.end();++x)

#define ULL unsigned long long

#define PI 3.1415926535

#define INF 0x3f3f3f3f

#define LL long long

const int maxn = 1e3+5;

const int mod = 1e9 + 7;

const double eps = 1e-8;

using namespace std;

int main(){

//freopen("in.txt", "r", stdin);

//freopen("out.txt", "w", stdout);

int n,ans=1,maxx=0;

scanf("%d",&n);

for(int i=2;i<=n;++i){

int tmp=i,tmp1=1,tmp2=0;

while(tmp%2==0) tmp/=2;

while(tmp%5==0) tmp/=5;

if(tmp==1)

tmp2=0;

else{

do{

tmp1=tmp1*10%tmp;

++tmp2;

}while(tmp1!=1);

}

//printf("%d\n",tmp2);

if(tmp2>maxx){

maxx=tmp2;

ans=i;

}

}

printf("%d\n",ans);

return 0;

}

另一种模拟除法的做法如下：

#include<iostream>

#include<string.h>

using namespace std;

int d[1000000];

int fun(int x){

int k=1,l=1;

memset(d,0,sizeof(d));

while(1){

k*=10;

k%=x;

d[k]++;

l++;

if(d[k]==2||k==0) break;

}

return l;

}

int main(){

int n;

cin>>n;

int maxx=0,max=0;

for(int i=1;i<=n;i++){

if(fun(i)>maxx){

maxx=fun(i);

max=i;

}

}

cout<<max<<endl;

return 0;

}

巴特西

51 Nod 1035 最长的循环节（此题还不是很懂，日后再看）

转自：

51nod 1035 最长的循环节(无限小数的循环节)

定理

代码

最新文章

热门文章

巴特西

51 Nod 1035 最长的循环节 （此题还不是很懂，日后再看）

转自：

51nod 1035 最长的循环节(无限小数的循环节)

定理

代码

最新文章

热门文章

51 Nod 1035 最长的循环节（此题还不是很懂，日后再看）