POJ 1047 Round and Round We Go 循环数新解

furney · · 2063 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目描述:

给定一字符串表示的高精度数,判断它是否是可循环的。如果假设字符串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;
}




有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:furney

查看原文:POJ 1047 Round and Round We Go 循环数新解

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2063 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传