ACM模版

描述

题解

对于数论只会打表找规律的我来说，我一上来就打了一张表，然后发掘其中的规律……没法子，脑子跟不上，推不出来规律，只能找规律。

通过这个表我们可以发现：
从第100项到51项是等差数列0~49，base = 1；
从第50项到34项是等差数列0~32，base = 2；
从第33项到26项是等差数列1~22，base = 3；
……

所以我们可以发现，这是由项数递减的若干等差数列构成的，而这个项数满足 N - x = st + base * x，化简也就是说项数 x = (N - st) / (base + 1)，这里需要注意的是向上取整才行，至于为什么，自己模拟试试就知道了，另外还需要注意的是这里可能会超 long long，所以需要用到乘法逆元，也就是 2 对 MOD 的逆元，因为求等差数列的和时涉及到了一个除以 2 的操作，在这里，由于只用到了这一个逆元，所以直接 const 一个值表示它即可，也就是 5e8 + 4，GG！

代码

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int MOD_2 = 5e8 + 4;

int main(int argc, const char * argv[])
{
    long long N, M;
    cin >> N;
    M = N;

    long long res = 0;
    long long base = 1;
    long long st = 0;
    long long x, ed;

    while (M > 0)
    {
        x = (M - st) / (base + 1);
        if (x == 0)
        {
            break;
        }
        if ((base + 1) * x != M - st)    // 向上取整
        {
            x++;
        }

        ed = st + (x - 1) * base;

        res = (res + ((st + ed) % MOD * (x % MOD)) % MOD * MOD_2 % MOD) % MOD;

        M -= x;
        if (M == 0)
        {
            break;
        }

        st = (ed + base) % M;
        base++;
    }

    for (int i = 1; i <= M; i++)
    {
        res = (res + N % i) % MOD;
    }

    cout << res << '\n';

    return 0;
}