Project Euler 26 Reciprocal cycles

题意：求1到n中所有数的倒数中循环小数循环体最长的数

解法：如果一个数的质因子只有2和5，那么这个数的倒数一定不是一个循环小数。如果一个数含有质因子2或5，那么它的循环体和去掉质因子2和5之后的数的循环体是一样长的，如3和6。对于一个质因子没有2和5的数，能被几个9组成的数整除它的循环体就有多长，如1 / 7 = 0.(142857)，999999 / 7 = 142857。

对于这个例子我做了简单的证明：

因为1 / 7 = 0.(142857)，所以1000000 / 7 = 142857.(142857) = 142857 + 0.(142857) = 142857 + 1 / 7

所以999999 / 7 = 142857

代码：

循环体比较长……用了Java大数

package pe0026;

import java.math.*;

public class main

{

	public static void main(String[] args)

	{

		int maxn = 0, pos = 0;

	    for(int i = 2; i <= 1000; i++)

	    {

	        if(i % 2 == 0 || i % 5 == 0)

	            continue;

	        BigInteger x = BigInteger.ZERO;

	        int cnt = 1;

	        while(true)

	        {

	            x = x.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(9));

	            cnt++;

	            if(x.mod(BigInteger.valueOf(i)) == BigInteger.ZERO)

	            {

	                if(maxn < cnt)

	                {

	                    maxn = cnt;

	                    pos = i;

	                }

	                break;

	            }

	        }

	    }

	    System.out.println(pos);

	}

}

巴特西

Project Euler 26 Reciprocal cycles

最新文章

热门文章