p017 Ones

紿任一個整數 n（1 <= n <= 9999），且 n 不可被 2 或 5 除盡。n的某一個倍數以十進位的表示法將是一連串的1，請問這一連串的1最少是幾位數？

例如：

n=3，3*37=111，所以答案是3位數。

n=7，7*15873=111111，所以答案是6位數。

解法：
都是大於等於1的數字，所以一定有一個連續的1而且只有一位數就是1本身。
所以我們先暫定我們要求的數字為tmp = 1，且位數digits = 1
每次都將tmp*10 + 1的目的是我們希望最後一位數都會是1，這樣一來才能產生連續1的數字
而在乘10的同時代表說我們也要digits++，因為一定是再更高位的連續1數字了！
如果終於能夠整除了，就能確定說tmp就是我們要找的數字了。

/**
 * Time(ZeroJudge):78ms
 * Date: 2010-1-28
 * 
 * @author Kurorido
 */

import java.util.Scanner;

public class JAVA {

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  
  int n, tmp, digits;
  
  while(sc.hasNext()) {
   
   n = sc.nextInt();
   tmp = 1;
   digits = 1;
   
   while(true) {
    if(tmp % n == 0)
     break;
    tmp = (tmp * 10 + 1) % n;
    digits++;
   }
   
   System.out.println(digits);
  }
 }
}

參考網站：
http://groups.google.com.tw/group/pcshic/web/uva-10127-ones
http://hi.baidu.com/ly01kongjian/blog/item/d21e666f4734f5f1421694a8.html