题意
正整数k的倒数1/k,写为10进制的小数如果为无限循环小数,则存在一个循环节,求<=n的数中,倒数循环节长度最长的那个数,假如存在多个最优的答案,输出所有答案中最大的那个数。
1/6= 0.1(6) 循环节长度为1 1/7= 0.(142857) 循环节长度为6 1/9= 0.(1) 循环节长度为1
解题思路
模拟求出1~1000内所有循环节长度。求循环节通过判断余数出现的次数来确定是否出现循环节。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[
1005];
int b[
100000];
int ans[
1005];
void Init(){
for (
int n=
1;n<
1005;n++){
memset(a,
0,
sizeof(a));
int left=
1,cnt=
0;
while (left<n){
left*=
10;
}
while (left){
if (left>n) left%=n;
b[cnt++]=left;
a[left]++;
if (a[left]>
1)
break;
left*=
10;
}
ans[n]=
0;
for (
int i=
0;i<cnt-
1;i++){
if (left==b[i]){
ans[n]=cnt-i-
1;
break;
}
}
}
}
int main(){
int n;
Init();
while (
cin>>n){
int Max=
0,Index=-
1;
for (
int i=
1;i<=n;i++){
if (Max<ans[i]){
Max=ans[i];
Index=i;
}
}
cout<<Index<<endl;
}
return 0;
}