【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解

题目描述:

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

}

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-02-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏偏前端工程师的驿站

JS魔法堂:再识Number type

Brief                                   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

2205
来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

2005
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2555
来自专栏Jackson0714

C# 正则表达式

1172
来自专栏noteless

[十一]基础数据类型之Character

该类提供了几种方法来确定字符的类别(小写字母、数字等),并将字符从大写转换为小写,反之亦然

841
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

661
来自专栏Jackson0714

C# 正则表达式

5175
来自专栏赵俊的Java专栏

快乐数

2473
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4425
来自专栏恰童鞋骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

823

扫码关注云+社区

领取腾讯云代金券