首页 > 代码库 > 51Nod - 1035 最长的循环节
51Nod - 1035 最长的循环节
51Nod - 1035 最长的循环节
正整数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示例
10
Output示例
7
题解:
使用直接方法。用 map 来辅助计算循环节。
#include <iostream> #include <map> using namespace std; const int MAXN = 1000 + 5; int cnt[MAXN]; int Find(int n){ int num = 1, idx = 1, ans; map<int, int> mp; while(1){ if(num == 0){ return 0; } while(num < n){ num = num * 10; } if(mp.find(num) == mp.end()){ mp[ num ] = idx; idx++; }else{ ans = idx - mp[ num ]; break; } num = num % n; } return ans; } void init(){ for(int i=2; i<=1000; ++i){ cnt[i] = Find(i); } } int main(){ int n, ans, ans_tmp; init(); while(scanf("%d", &n) != EOF){ ans = 0, ans_tmp = 0; for(int i=1; i<=n; ++i){ if(ans_tmp < cnt[i]){ ans_tmp = cnt[i]; ans = i; } } printf("%d\n", ans ); } return 0; }
51Nod - 1035 最长的循环节
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。