p028 Factovisors

• 任何數字都可以被表達成質因數分解式
• b|a <=> a = kb

所以要確認某個數是否可以整除該階乘數的話，檢查該數的質因數分解的質數次方是否小於階乘數內的質數次方

假設我們想知道12是否可以整除6!

1. 我們先把12分解成12 = 2^2 * 3^1
2. 接下來我們呼叫一些方法來得知階乘數內的質數次方
   int get_powers(n,p)
   呼叫一次求2在6!的次方，得到2^4，又4 > 2
   呼叫一次求3在6!的次方，得到3^2，又2 > 1

毋庸置疑的，12可以整除6!

要注意以下幾點：

• 0 整除 n! 是錯誤的
• m 整除 n! 恆真當 m 小於等於 n

該如何撰寫get_powers(n,p)函式？

例如說6!中要找2的次方，我們就從1走到6，為了要紀錄有幾個次方，我們用一個power的變數來計算
當在1的時候1 % 2 != 0，無視
當在2的時候2 % 2 = 0, 這次我們就可以把power++
當在4的時候4 % 2 = 0, 我們先把power++之後再將4/2與2求餘一次，又可以再power++一次
當在6的時候6 % 2 = 0, power++
最後得到power為4回傳

/**
 * Time(ZeroJudge): 94 ms
 * Date: 2010-01-28
 * 
 * @author Kurorido
 */

import java.util.Scanner;

public class JAVA {

 public static void main(String[] args) {
  
  Scanner sc = new Scanner(System.in);
  boolean debug = false;
  
  while(sc.hasNext()) {
   
   int n = sc.nextInt();
   int b = sc.nextInt();
   boolean flag = true;
   
   int[][] present = represent(b);
   if(debug)
    for(int i = 0; i < present.length; i++) {
     for(int j = 0; j < present[i].length; j++) {
      System.out.print(present[i][j] + " ");
     }
     System.out.println();
    }
   
   for(int i = 0; i < present.length; i++) {
    if(get_powers(n, present[i][0]) < present[i][1]) {
     flag = false;
     break;
    }
   }
   
   if(flag)
    System.out.println(b + " divides " + n +"!");
   else
    System.out.println(b + " does not divide " + n +"!");
  }
 }
 
 public static int[][] represent(int num) {
  
  int limit = num+1;
  int[] list = new int[limit];
  int count = 0;   // count how many primes
  int max = 0;  // remember max, for reuse
  for(int i = 2; i < limit; i++) {
   if(num % i == 0) {
    count++;
    max = i;
   }
   while(num % i == 0) {
    if(num == 0)
     break;
    num = num / i;
    list[i]++;
   }
  }

  // make a present, use count size
  int[][] present = new int[count][2];
  count = 0;
  // reuse max, because max is the biggest primes.
  for(int i = 2; i <= max; i++) {
   if(list[i] > 0) {
    present[count][0] = i;
    present[count][1] = list[i];
    //System.out.println(present[count][0] + " " + present[count][1]);
    count++;
   }
  }
  
  return present;
 }
 
 public static int get_powers(int n, int p) {
  
  if(n == 1)
   return 0;
  
  int power = 0;
  
  for(int i = 1, num = i; i < n; i++, num++) {
   
   while(num % p == 0) {
    if(i == 0)
     break;
    num = num / p;
    power++;
   }
  }
  
  return power;
 }
}

比Java排行榜的最快速度慢了20ms....等誰來改改吧= =