第一周训练赛 A-Numbers

https://codeforces.com/problemset/problem/13/A

题目描述

Little Petya likes numbers a lot. He found that number 123 in base 16 consists of two digits: the first is 7 and the second is 11. So the sum of digits of 123 in base 16 is equal to 18.

Now he wonders what is an average value of sum of digits of the number A written in all bases from 2 to A - 1.

Note that all computations should be done in base 10. You should find the result as an irreducible fraction, written in base 10.

求10进制数 A 的 2~A-1 进制的所有数字之和的平均值。

举例

例如 10进制数 5
则求其 2 3 4 进制数—— 101 12 11
数字之和分别为—— 2 3 2
平均数为 7/3

思路

用数组s储存转化进制后每个数位上的数字 例如：5的2进制，则s中有{1，0，1}
用数组sum存储转化进之后各进制的数字之和 例如 5的所有进制数字之和sum{2，3，2}
all_sum 储存数字总和，即 5的all_sum = 7
最后求 7 和 5-2的最大公约数，对分数7/3进行化简

改进：去掉sum数组，求出的数字直接进行加和

代码

测试超时代码

#include <iostream>
#include <string.h>


#define ARRAY_SIZE 100 //数组储存空间的初始分配量
#define ARRAYINCREMENT 10 //数组储存空间的分配增量

using namespace std;

//最大公约数
int gcd(int n, int m) {
    if (m == 0) return n;
    else if (n % m == 0) return m;
    else return gcd(m, n % m);
}

//十进制转换为任意进制
bool decimal_conversion(int dec, int m, int* s) {
    //dec十进制数，m转换进制，s存放各位数字
    int i = 0;
    while (dec != 0) {
        s[i] = dec % m;
        dec /= m;
        i++;

        //s内存判断
        if (i > (sizeof(s) / sizeof(s[0]))) {
            s = (int*)realloc(s, ((sizeof(s) / sizeof(s[0])) + ARRAYINCREMENT) * sizeof(int));
            if (!s) return false;//分配失败
        }
    }
    s[i] = -1;
    return true;
}

//进制数加和
void func_sum(int* s, int* sum, int i) {
    int k = 0;
    while (s[k] != -1) {
        sum[i] += s[k];
        k++;
    }
}

//进制数求平均值
void func_average(int* sum, int n) {
    long long all_sum = 0;
    for (int i = 0; i < n; i++) {
        if(sum[i] != -1)
        all_sum += sum[i];
    }
    //约分
    cout << all_sum / gcd(all_sum, n) << "/" << n / gcd(all_sum, n) << endl;
}

void test() {
    int dec = 0;
    int* s = new int[ARRAY_SIZE]{};
    while (cin >> dec) {
        int* sum = new int[dec - 2]{};
        int i = 0;
        for (int m = 2; m <= dec - 1; m++) {
            decimal_conversion(dec, m, s);
            func_sum(s, sum, i++);
        }
        sum[i] = -1;
        func_average(sum, dec - 2);
    }
}

int main() {
    test();
    return 0;
}

改进后 通过代码

#include <iostream>
#include <string.h>


#define ARRAY_SIZE 100 //数组储存空间的初始分配量
#define ARRAYINCREMENT 10 //数组储存空间的分配增量

using namespace std;

//最大公约数
int gcd(int n, int m) {
    if (m == 0) return n;
    else if (n % m == 0) return m;
    else return gcd(m, n % m);
}

//十进制转换为任意进制
bool decimal_conversion(int dec, int m, int* s) {
    //dec十进制数，m转换进制，s存放各位数字
    int i = 0;
    while (dec != 0) {
        s[i] = dec % m;
        dec /= m;
        i++;

        //s内存判断
        if (i > (sizeof(s) / sizeof(s[0]))) {
            s = (int*)realloc(s, ((sizeof(s) / sizeof(s[0])) + ARRAYINCREMENT) * sizeof(int));
            if (!s) return false;//分配失败
        }
    }
    s[i] = -1;
    return true;
}

//进制数加和
long long func_sum(int* s) {
    int k = 0;
    long long sum = 0;
    while (s[k] != -1) {
        sum += s[k];
        k++;
    }
    return sum;
}

//进制数求平均值
void func_average(long long all_sum, int n) {
    //约分
    cout << all_sum / gcd(all_sum, n) << "/" << n / gcd(all_sum, n) << endl;
}

void test() {
    int dec = 0;
    long long all_sum = 0;
    int* s = new int[ARRAY_SIZE]{};
    while (cin >> dec) {
        all_sum = 0;
        int i = 0;
        for (int m = 2; m <= dec - 1; m++) {
            decimal_conversion(dec, m, s);
            all_sum +=func_sum(s);
        }
        func_average(all_sum,dec - 2);
    }
}

int main() {
    test();
    return 0;
}

测试