2017京東校招筆試程式設計題：進制轉換、輾轉相除

題目描述：

時間限制：C/C++語言 1000MS 其他語言：3000MS

記憶體限制：C/C++語言 65536KB 其他語言：589824KB

題目内容：盡管是一個CS專業的學生，小B的數學基礎很好并對數值計算有着特别的興趣，喜歡用計算機程式來解決數學問題。現在，她正在玩一個數值變換的遊戲。她發現計算機中經常用不同的進制表示同一個數，如十進制數123表達為16進制時隻包含兩位數7、11（B），用八進制表示時為三位數1、7、3。按不同進制表達時，各個位數的和也不同，如上述例子中十六進制和八進制中各位數的和分别是18和11。小B感興趣的是，一個數A如果按2到A-1進制表達時，各個位數之和的平均值是多少？她希望你能幫她解決這個問題。所有的計算均基于十進制進行，結果也用十進制表示為不可約簡的分數形式。

輸入：輸入中有多組測試資料。每組測試資料為一個整數A（1<=A<=5000）。

輸出：對每組測試資料，在單獨的行中以X/Y的形式輸出結果。

樣例輸入：

5

3

樣例輸出：

7/3

2/1

具體實作

題目相對比較簡單，主要是實作兩個函數，一個是10進制到任意進制間的轉換；另一個是求解兩個數的最大公約數。

直接貼代碼：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    //10進制轉換任意進制,并将每位數字存入list中,傳回各位數字之和
    public static int transForm(int num, int n){
        List<Integer> list = new ArrayList<>();
        int sum = ;
        while(num != ){
            int remainder = num%n;
            num = num/n;
            list.add(remainder);
        }

        //計算進制轉換後所得結果各位數字之和
        for(int i = ; i < list.size(); i++){
            sum += list.get(i);
        }
        return sum;
    }

    //輾轉相除,計算兩個數的最大公約數
    public static int gcd(int m, int n){
        int r = m % n;
        while (r != ){
            m = n;
            n = r;
            r = m % n;
        }
        return n;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int sum = , div;
        div = m - ;    // 分子
        for(int i = ; i < m; i++){
            sum += transForm(m, i);
        }
        System.out.println(sum/gcd(sum, div) + "/" + div/gcd(sum, div));
    }
}