CF1542C-Strange Function

2022-04-21 题解

题目大意：定义 $f(x)$ 为“不能被x整除的最小正整数”，给定n，求

\sum_{i=1}^{n}f(i)

如果 $f(i)=x$ ，那么 $i$ 是 $1,2,3,4,5,...,x-1$ 这x-1个数的公倍数，即这x-1个数的最小公倍数的若干倍。假设这x-1个数的最小公倍数为 $lcm$ ，那么总共的n个数中一共有 $n \div lcm$ 个这x-1个数的公倍数，那么这x-1个数的 $f$ 值都至少为x。

所以可以写出代码

#include <bits/stdc++.h>
using namespace std;
long long lcm(long long x, long long y)
{
    return x / __gcd(x, y) * y;
}
int main()
{
    int _;
    long long x, sum, res, i;
    const long long mod = 1e9 + 7;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%lld", &x);
        for (sum = 2, i = 2, res = x << 1; sum <= x; sum = lcm(sum, i))
            res = (res + x / sum) % mod, i++;
        printf("%lld\n", res);
    }
    return 0;
}