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...阅读全文