51nod - 1035 最长的循环节(数论)

51nod - 1035 最长的循环节

题目

给一个n，（10<= n <= 1000）,求小于n的数num，$1/num$化成小数循环节长度最大的num。

分析

定理：

如果$1<=b<a$,a没有2或5的质因子，并且a与b互质，那么$b/a$的循环节位数恰好等于使下式成立最小的k。$$10^k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}a)$$

如果1<=b<a,a没有2或5的质因子，并且a与b互质，那么$b/a$的循环节位数必整除$\varphi (a)$

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define d(x) cout << (x) << endl #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int M = 2e2 + 10; const int N = 1e3 + 10; int n; int ans[N]; //预处理前1000项 void init() { for(int i = 2; i <= 1000; i++){ int num = i; ans[i] = 1; while(num % 2 == 0) num /= 2; while(num % 5 == 0) num /= 5; for(int j = 1; j <= num; j++){ ans[i] = ans[i] * 10 % num; if(ans[i] == 1){ ans[i] = j; break; } } } } int main() { init(); scanf("%d", &n); int maxn = -INF; int id; for(int i = 2; i <= n; i++){ //找最大的一项 if(ans[i] > maxn){ id = i; maxn = ans[i]; } } printf("%d\n", id); return 0; }