题目：ACwing

解题思路

1.明确题意

题目要求一个大于10进制整数A转换成2~A-1进制，并且把进制转化后的数字的各个位数相加，并将最后结果除以A-2

2.解题步骤

1）把10进制数转换为其它进制数，采用比较朴素的辗转相除法，求出进制转换后的每一位数是多少。

代码

1
2
3
4
void base(int n, int i)
{
    while (n) { sum += n % i, n /= i; }
}

如把212转化为七进制

F090CA846E06397E0532E0C77CC70147.jpg

验证

B7696F80F2A0B42D3E4389E188DB1A68.jpg

2）因为结果输出要除A-2，所以我们采用欧几里得算法求解其最大公约数，让两者分别除自己的最大公约数后再输出

欧几里得算法的核心公式：gcd(a,b) = gcd(b,a mod b)。

1
2
3
4
5
int gcd(int a, int b)
{
    if(a % b == 0) return b;
    return gcd(b, a % b);
}

3）欧几里得例子：假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

3.完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>

using namespace std;

int n, sum;

void base(int n, int i)
{
    while (n) { sum += n % i, n /= i; }
}

int gcd(int a, int b)
{
    if(a % b == 0) return b;
    return gcd(b, a % b);
}

int main()
{
    scanf("%d", &n);

    for (int i = 2; i <= n - 1; i ++ ) base(n, i);

    int a = sum, b = n - 2;
    int c = gcd(a, b);

    printf("%d/%d", a / c, b / c);

    return 0;
}