51nod 1035：最长的循环节

1035 最长的循环节

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

正整数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)

Output

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

Input示例

Output示例

这个问题的另一种描述:给定大整数n(可能是质数也可能是合数,且不知道这个数的分解形式),求最小的k使10^k ≡1 (mod n)。一开始不懂这个。后来想了一想，就是一开始的余数是1啊。

扣掉5，扣掉2。剩下的数模拟一下除法，一开始的余数就是一开始的被除数1，什么时候余数又回到1了，就说明循环节的长度是多少了。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int euler(int n)
{
	int res = n, a = n;
	for (int i = 2; i*i <= a; i++)
	{
		if (a%i == 0)
		{
			res = res / i*(i - 1);
			while (a%i == 0)a /= i;
		}
	}
	if (a > 1)res = res / a*(a - 1);
	return res;
}

int res[1005];

int main()
{
	memset(res, 0, sizeof(res));

	int i, temp, j, k, n;
	for (temp = 1; temp <= 1000; temp++)
	{
		i = temp;
		while (i % 2 == 0)
		{
			i /= 2;
		}
		while (i % 5 == 0)
		{
			i /= 5;
		}
		k = euler(i);
		n = 1;
		for (j = 1; j <= i; j++)
		{
			n *= 10;
			n %= i;
			if (n == 1)
			{
				res[temp] = j;
				break;
			}
		}
	}
	int max_re ;
	while (cin >> n)
	{
		max_re = 1;
		for (i = 1; i <= n; i++)
		{
			if (res[i] > res[max_re])
				max_re = i;
		}
		cout << max_re << endl;
	}
	return 0;
}