京东-进制均值

枚举所有进制的和cnt，以及进制个数n-2
进制转换：除法倒排
求cnt和n-2的最大公约数，辗转相除法，递归法理解起来更为容易,并且容易优化
最小公倍数为x*y/gcd(x,y)

import java.util.*;
public class Main{
     //以y为进制的数位和
    public static int sum(int x,int y){
        int cnt=0;
        while(x>0){
            cnt+=x%y;
            x/=y;
        }
        return cnt;
    }
    //辗转相除法求的最大公约数
    public static int gcd(int x,int y){
        if(x==y){return x;}
        return x-y>y?gcd(x-y,y):gcd(y,x-y);
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            int n=sc.nextInt();
            int cnt=0;
            for(int i=2;i<n;i++){
                cnt+=sum(n,i);
            }
            int t=gcd(cnt,n-2);
            System.out.println((cnt/t)+"/"+((n-2)/t));
        }
    }

}