【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解
【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解
李海彬
发布于 2018-03-20 10:18:44
发布于 2018-03-20 10:18:44
题目描述：
给定一字符串表示的高精度数，判断它是否是可循环的。如果假设字符串num的长为n，则将num从1开始乘到n，如果每次得到的结果包含的字符元素都和a是相同的，则它是可循环的。
解题思路：
初看这一题，想到的解法是利用高精度数的乘，计算出num乘以1到n的结果，再与num进行对比。这种方法较为简单，可以得到正确的结果，但是效率并不是很理想。对于循环数，我们最常见到的是循环小数，而这一题的解法也是由此引申得出的。
初等数论里面有以下三个定理：
欧拉定理：设a、m为整数，m>1，(a,m)=1，则a^φ(m)≡1 (mod m)。 整数的次数：a、m为整数，m>1，(a,m)=1，k是使a^k≡1 (mod m)成立的最小正整数，则k叫做a对模m的次数。 次数定理：设a对模m的次数为k，n是满足a^n≡1 (mod m)的正整数，则k|n。
这三个定理的证明在数论书里面都有介绍，想详细了解的可以自己去查阅。利用上面的定理有：
1/7=0.142857142857...
循环节的位数为6，将上式乘以10^6得
=>10^6/7=142857.142857142857...
=>(10^6-1)/7=142857
=>999999/7=142857
对于其他的数num，如果其位数是n，如果num*(n+1)得到的结果是n个9，那么这个数就是可循环的。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string num;
bool flag = true;
int i, n, c, t;
while(cin >> num)
{
flag = true;
n = num.size() + 1;
c = 0; t = 0;
for(i = n - 2; i >= 0; i--)
{
t = num[i] - '0';
if((t * n + c) % 10 != 9) //判断结果是否全为9
{
flag = false;
break;
}
c = (t * n + c) / 10;
}
if(flag)
{
cout << num << " is cyclic" << endl;
}
else
{
cout << num << " is not cyclic" << endl;
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2016-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读