最长循环节模版

博主链接

//正整数k的倒数1/k，写为10进制的小数如果为无限循环小数，
//则存在一个循环节，求<=n的数中，倒数循环节长度最长的那个数，
//假如存在多个最优的答案，输出所有答案中最大的那个数。 

/*

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

*/

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
using namespace std;
const int maxn = 1e6 + 7;
int main(int argc, char *argv[]) {
	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);
		}
		if (tmp2 > maxx) {
			maxx = tmp2;
			ans = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}