首页 > 代码库 > 1035 最长的循环节
1035 最长的循环节
1035 最长的循环节
基准时间限制:1 秒 空间限制:131072 KB
正整数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
思路:转换为求最小的k使10^k ≡1 (mod n)。就是一开始的余数是1。
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <vector> 5 #include <string> 6 #include <cstring> 7 #include<stdlib.h> 8 #include<stdio.h> 9 using namespace std;10 int main(void)11 {12 int n;13 scanf("%d",&n);14 int minn = 0;15 int i,j;16 int maxx = 0;17 for(i = 3 ; i <=n ; i++)18 {19 int t = 1;int flag = 0;20 for(j = 1; j <= i ; j++)21 {22 t*=10;//if(i==7)printf("%d\n",t);23 if(t%i==0)24 break;25 else if(t%i == 1)26 {27 flag = j;28 break;29 }30 t%=i;31 }32 if(flag > minn)33 {34 minn = flag;35 maxx = i;36 }37 }38 printf("%d\n",maxx);39 return 0;40 }
1035 最长的循环节
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。