欧拉计划第26题
作者:
brivia
,
2024-02-25 15:25:54
,
所有人可见
,
阅读 39
/*
欧拉计划第26题,找出1~1000中的一个自然数d, 使得1/d的循环节最长。
模拟手算除法操作, 当被除数重复出现时,表示已经有循环了。
todo: 如何将分数表示成 0.ab(cde)这种模式。
*/
#include<bits/stdc++.h>
using namespace std;
int f(int d)
{
// 1/d 循环节有几位
int ans = 0;
map<int, int> a;
int k = 10;
int i = 0;
while (1)
{
if (!k) break;
i ++; // 小数点后第几位
if (a[k])
{
//以前出现过 k
ans = i - a[k];
break;
}
a[k] = i;
//cout << k / d;
k = (k % d) * 10;
}
//cout << endl;
return ans;
}
using namespace std;
int main(void)
{
int maxlen = 0, ans = -1;
for (int i = 1; i <= 1000; ++ i)
if (f(i) > maxlen)
{
maxlen = f(i);
ans = i;
}
cout << ans << " " << maxlen << endl;
//cout << f(983) << endl;
//cout << f(997) << endl;
return 0;
}