每日一题2

Question

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:    1/2 =  0.5
    1/3 =  0.(3)
    1/4 =  0.25
    1/5 =  0.2
    1/6 =  0.1(6)
    1/7 =  0.(142857)
    1/8 =  0.125
    1/9 =  0.(1)
    1/10 =  0.1Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.最长的无限循环小数循环部分

Answer 1

是用笨方法在质数里面硬算的using System;
using System.Collections.Generic;namespace ConsoleApplication6
{
    class Program
    {
        static void Main()
        {
            int[] primes = GetPrimeList(1000);
            int max = 0;
            int num = -1;            for (int i = 0; i < primes.Length; i++)
            {
                int count = GetCount(primes[i]);
                
                if (count > max)
                {
                    max = count;
                    num = primes[i];
                }
            }            Console.WriteLine("{0} {1}", num, max);
            Console.ReadKey();
        }        static private int[] GetPrimeList(int upperValue)
        {
            List<int> PrimeList = new List<int>();
            bool[] flags = new bool[upperValue + 2];            for (int i = 2; i <= (int)Math.Sqrt(upperValue); i++)
            {
                if (!flags[i])
                    for (int j = i * i; j <= upperValue; j += i)
                        flags[j] = true;
            }            for (int i = 2; i < upperValue; i++)
                if (!flags[i])
                    PrimeList.Add(i);            return PrimeList.ToArray();
        }        static int GetCount(int num)
        {
            bool[] flag = new bool[num];            int i = 1;
            int count = 0;            while (true)
            {
                if (flag[i] || i == 0)
                    break;
                else
                    flag[i] = true;                if (i < num)
                    i *= 10;
                
                i = i % num;                count++;
            }            return count;
        }
    }
}

Answer 2

修改了一下，倒着来快了很多，算10000也可以的。using System;
using System.Collections.Generic;namespace ConsoleApplication6
{
    class Program
    {
        static void Main()
        {
            int[] primes = GetPrimeList(1000);
            int max = 0;
            int num = -1;            for (int i = primes.Length - 1; i >= 0; i--)
            {
                int count = GetCount(primes[i]);
                
                if (count > max)
                {
                    max = count;
                    num = primes[i];
                }                if (primes[i] <= max)
                    break;
            }            Console.WriteLine("{0} {1}", num, max);
            Console.ReadKey();
        }        static private int[] GetPrimeList(int upperValue)
        {
            List<int> PrimeList = new List<int>();
            bool[] flags = new bool[upperValue + 2];            for (int i = 2; i <= (int)Math.Sqrt(upperValue); i++)
            {
                if (!flags[i])
                    for (int j = i * i; j <= upperValue; j += i)
                        flags[j] = true;
            }            for (int i = 2; i < upperValue; i++)
                if (!flags[i])
                    PrimeList.Add(i);            return PrimeList.ToArray();
        }        static int GetCount(int num)
        {
            bool[] flag = new bool[num];
            int i = 1;
            int count = 0;            while (true)
            {
                if (flag[i] || i == 0)
                    break;
                else
                    flag[i] = true;                if (i < num)
                    i *= 10;
                
                i = i % num;
                count++;
            }            return count;
        }
    }
}

Answer 3

哈哈 public static void main(String[] args) {
Integer[] primeNumber = getPrimeNumber(1000000);
        int max = 0;
        int num = 0;
        for (int i = primeNumber.length - 1; i >= 0; i--){
            int count = GetCount(primeNumber[i]);
            if (count > max){
                max = count;
                num = primeNumber[i];
            }
            if(primeNumber[i] <= max)
             break;
        }
        System.out.printf("1/%d ===> %d", num, max);
} private static int GetCount(int num) {
boolean[] flag = new boolean[num];
int i = 1;
int count = 0;
while (true) {
if (flag[i] || i == 0)
break;
else
flag[i] = true;
if (i < num)
i *= 10;
i = i % num;
count++;
}
return count;
} private static Integer[] getPrimeNumber(int maxNum) {
HashSet<Integer> set = new HashSet<Integer>();
boolean[] notPrimeNum = new boolean[maxNum + 1];
for (int i = 2; i <= notPrimeNum.length / 2; i++) {
for (int j = 2; j <= i && i * j < notPrimeNum.length; j++) {
notPrimeNum[i * j] = true;
}
}
for (int i = 3; i < notPrimeNum.length; i++) {
if (!notPrimeNum[i])
set.add(i);
}
Integer[] result = new Integer[set.size()];
set.toArray(result);
Arrays.sort(result);
return result;
}

Answer 4

public class DivideTest {    public static void main(String[] args) {
        String biggestPart = "";
        int biggestNumber = 0;
        
        String part1 = getRepeatePart(2);        biggestPart = part1;
        biggestNumber = 1;
        
        for(int i=3;i<1000-1;i++){
            String part2 = getRepeatePart(i);
            if(biggestPart.length() < part2.length()){
                biggestPart = part2;
                biggestNumber = i;   
            }
        }
        System.out.println(biggestNumber);//983
        System.out.println(biggestPart);
    }
    private static String getRepeatePart(int fenMu) {
        
        StringBuffer result = new StringBuffer();
        result.append("0.");
        
        List fenZiList = new ArrayList();
        int fenZi=1;
 
        fenZiList.add(Integer.valueOf(fenZi));
        
        while(fenZi < fenMu){
            fenZi = fenZi*10;
            int yuShu = fenZi % fenMu;
            if(yuShu == 0)return "";
            int shang = fenZi / fenMu;
            result.append(shang);
            fenZi = yuShu;
            int  repeateIndex = findRepeateIndex(fenZiList,fenZi);
            if(repeateIndex>=0){
                return result.substring(repeateIndex+2);
            }else{
                fenZiList.add(Integer.valueOf(fenZi));
            }
        }
        return ""; 
    }    private static int findRepeateIndex(List fenZiList,int fenZi) {
        for(int i=0;i<fenZiList.size();i++){
            int fz = ((Integer)fenZiList.get(i)).intValue();
            if(fz == fenZi){
                return i;
            }
        }
        return -1;  
    }
}

Answer 5

哎
偷用 litaoye 的代码
变量名和方法名忘改了 杯具啊

Answer 6

呵呵 还是说说原理吧
10^min - 1 = n * k (k为正整数)
满足这个条件最小的min就是循环节的长度

Answer 7

就是10F的样子。983
int[] primes = new int[] {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
        149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
        227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
        307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
        389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
        467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
        571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
        653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
        751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
        853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
        947, 953, 967, 971, 977, 983, 991, 997
    };
    int result = 0;
    int maxLength = 0;
    for (int prime : primes) {
      int length = 0;
      boolean[] remainderOccurred = new boolean[prime];
      for (int remainder = 1; ;) {
        remainder *= 10;
        remainder %= prime;
        if (remainder == 0 || remainderOccurred[remainder]) {
          break;
        }
        remainderOccurred[remainder] = true;
        length++;
      }
      if (length > maxLength) {
        maxLength = length;
        result = prime;
      }
      System.out.printf("1/%d, %d%n", prime, length);
    }
    BigDecimal value = BigDecimal.ONE.divide(BigDecimal.valueOf(result), maxLength, BigDecimal.ROUND_DOWN);
    System.out.printf("Result: d=%d, the longest recurring cycle is: %s", result, value);

Answer 8

wow，一下子那么多答案
不过我在想，我直接用质数是不是错误的

Answer 9

还记得小学时候怎么在草稿纸上算除法的吗？     .142857
   /------------
7 /  10
      7  <------------1: 1*10 mod 7 = 3
    -----
      30
      28  <-----------2: 3*10 mod 7 = 2
     -----
       20
       14  <----------3: 2*10 mod 7 = 6
      -----
        60
        56  <---------4: 6*10 mod 7 = 4
       -----
         40
         35  <--------5: 4*10 mod 7 = 5
        -----
          50
          49  <-------6: 5*10 mod 7 = 1
         -----
           1   <----- 又见1，循环重新开始

Answer 10

import java.util.Hashtable;public class Test {
public static String process(int n) {
String result;
Hashtable<Integer, Integer> flags = new Hashtable<Integer, Integer>();
StringBuilder stringBuilder = new StringBuilder();
int mod = 1 % n;
Integer flag;
for (int i = 0; ; i++) {
if (mod == 0) {
result = "1/" + n + " = " + (1d / n);
break;
}
flag = flags.get(mod);
if (flag != null) {
stringBuilder.insert(stringBuilder.indexOf(Integer.toString(mod * 10 / n), flag.intValue()), "(");
stringBuilder.append(")");
result = "1/" + n + " = 0." +  stringBuilder.toString();
break;
}
flags.put(mod, i);
stringBuilder.append(mod * 10 / n);
mod = (mod * 10) % n;
}
return result;
}

public static void main(String[] args) {
for (int i = 2; i < 1000; i++)
System.out.println(process(i));
}
}

Answer 11

查了些数学方面的资料，满足以下两点就可以：public static void main(String[] args) { System.out.println(getMaxCycle(1000));
} public static int getMaxCycle(int n){
int result = 1;
int temp = 1;
for(int i = 2; i <= n; i++){
temp = (getFactor(i) == 1)? temp : getCycle(BigInteger.valueOf(getFactor(i)));
if(temp >= result){
result = temp;
}
}
return result;
}

/**
 * 10^min - 1 = n * k (k为正整数),满足这个条件最小的min就是循环节的长度;
 * @param n
 * @return
 */
private static int getCycle(BigInteger n) {
int cycleValue = 1;
BigInteger divided = BigInteger.valueOf(10).subtract(BigInteger.valueOf(1));

while(divided.mod(n).intValue() != 0){
cycleValue++;
divided = BigInteger.valueOf(10).pow(cycleValue).subtract(BigInteger.valueOf(1));
}
return cycleValue;
} /**
 * 除去2，5因子
 * @param value
 * @return
 */
public static int getFactor(int value){
while (value%2 == 0) {
value /= 2;
}
while (value%5 == 0) {
value /= 5;
}
return value;
}