首页 > 代码库 > 51nod - 1035 最长的循环节
51nod - 1035 最长的循环节
点击查看题目
初看这题，还真的没什么思路（真是惭愧）。
然后看到了这篇论文：传送门
假设要求一个正整数倒数的循环节，其实最后是要求解一个最小的x满足 10x=1(mod C)
10x≡1(modC)
如果gcd(10,C)!=1的话，显然无解。如果存在解的话，根据欧拉公式，那么这个解 x|phi(C)，所以直接暴力枚举x就好了。
#include <bits/stdc++.h>using namespace std;int phi(int m) { int ans = m; for(int i=2; i*i<=m; i++) { if(m%i==0) { ans = ans / i * (i - 1); while(m%i==0) m /= i; } } if(m>1) ans = ans / m * (m - 1); return ans;}int fp(int a, int n, int p) { int r = 1; while(n) { if(n&1) r = r * a % p; a = a * a % p; n >>= 1; } return r;}int main() { int n; cin >> n; int ans = 0, cnt = 0; for(int p=7; p<=n; p++) if(__gcd(10, p) == 1) { int phn = phi(p); for(int i=1; i<=phn; i++) { if(phn%i == 0 && fp(10, i, p) == 1) { if(i>cnt) { cnt = i; ans = p; } break; } } } cout << ans << endl; return 0;}
x≡1(modC)
51nod - 1035 最长的循环节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。