andyli

题解 CF1213C 【Book Reading】
首先我们想到$Polycarp$写下的数字一定是循环的,因此我们可以计算对于所有$m$,他写下的数字的循环节里包含...
扫描右侧二维码阅读全文
01
2019/09

题解 CF1213C 【Book Reading】

首先我们想到$Polycarp$写下的数字一定是循环的,因此我们可以计算对于所有$m$,他写下的数字的循环节里包含数字的个数以及循环节所有数字的和。进行暴力打表或手算可以发现,$m(m>10)$上述结果和$m\% 10$的结果是如出一辙,因此我们只需打表出$0\leq m<10$的上述两个值,每次输入时计算$(n,m)$对应的所有循环节里数量的总和,再循环计算除去循环节以外其他写下的数字的和,相加即为最终答案。
代码如下:

#include <cstdio>

//int xhc[10] = { 0, 45, 20, 45, 20, 5, 20, 45, 20, 45 };
//int chx[10] = { 0, 10, 5, 10, 5, 2, 5, 10, 5, 10 };

int xhc[10]; // 循环节和
int chx[10]; // 循环节长度
int main()
{
    for (int i = 0; i < 10; i++) {
        int cnt = 1, sum = 0;
        for (int j = i; j; j = (j + i) % 10)
            cnt++, sum += j;
        xhc[i] = sum;
        chx[i] = cnt;
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        long long n, m;
        scanf("%lld%lld", &n, &m);
        if (m % 10 == 0)
            printf("0\n");
        else {
            int id = m % 10;
            // n / m - 整除数量
            // n / m / chx[id] - 循环数量 
            // n / m % chx[id] - 去除循环部分剩余数的数量
            // n / m / chx[id] * xhc[id] - 循环部分总和
            long long ans = n / m / chx[id] * xhc[id];
            int cnt = n / m % chx[id];
            for (int i = id; cnt--; i = (i + id) % 10)
                ans += i;
            printf("%lld\n", ans);
        }
    }
    return 0;
}
Last modification:November 23rd, 2019 at 11:28 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment