笔试刷题-京东2018-07-24

题目描述：

/**
尽管是一个CS专业的学生，
小B的数学基础很好并对数值计算有着特别的兴趣，
喜欢用计算机程序来解决数学问题，现在，她正在玩一个数值变换的游戏。
她发现计算机中经常用不同的进制表示一个数，
如十进制数123表达为16进制时只包含两位数7、11（B），
用八进制表示为三位数1、7、3，按不同进制表达时，各个位数的和也不同，
如上述例子中十六进制和八进制中各位数的和分别是18和11,。
小B感兴趣的是，
一个数A如果按2到A-1进制表达时，各个位数之和的均值是多少？
她希望你能帮她解决这个问题？
所有的计算均基于十进制进行，结果也用十进制表示为不可约简的分数形式。
输入描述:
输入中有多组测试数据，每组测试数据为一个整数A(1 ≤ A ≤ 5000).
输出描述:
对每组测试数据，在单独的行中以X/Y的形式输出结果。
输入例子1:
5
3
输出例子1:
7/3
2/1
*/

思路如下：

求最大公约数 约分

代码如下：

#include<stdio.h>
#include<iostream>
 
using namespace std;
 
int Gcd(int a, int b)
{
    if(a<0 || b<0)
        return -1;
    if(a==0)
        return b;
    if(b==0)
        return a;
    int minNum=min(a, b);
    int maxNum=max(a, b);
    if(maxNum%minNum==0)
        return minNum;
    return Gcd(maxNum%minNum, minNum);
}
 
int GetSum(int A)
{
    if(A<3)
        return -1;
    int sum=0;
    for(int base=2; base<A; base++)
    {
        int tempA=A;
        while(tempA)
        {
            sum+=(tempA%base);
            tempA/=base;
        }
    }
    return sum;
}
 
int main()
{
    int A;
    while(cin>>A)
    {
        if(A<0)
            return -1;
        if(A<3)
        {
            printf("0/%d", A-2);
        }
        else
        {
            int sum=GetSum(A);
            int gcdNum=Gcd(sum, A-2);
            printf("%d/%d\n", sum/gcdNum, (A-2)/gcdNum);
        }
    }
    return 0;
}