https://codeforces.com/problemset/problem/1542/C
题意:给定数字n,对于所有i∈[1, n], 找出第一个不被n整除的正数,计算这些正数的和。
思路:如果i是x的第一个不能整除的正整数,那么i - 1, i - 2,...1都能被x整除,可知,若要判断[1,n]范围内有多少数的第一个不能整除的数是多少,就是(n / lcm(1, 2, .. ,(x - 1)) - n / lcm(1, 2, ..., x)),其中的数量差就是第一个正整数为x的数字数量,再乘x累加倒答案中即可。要注意特殊情况,n = 1时,结果为2,n = 2时结果为3。
总结:出题人真nb
inline void solve() {long long n;cin >> n;MInt ans = 0;if (n == 1) {ans = 2;}else if (n == 2) {ans = 3;}long long g = 1;for (int i = 2; i <= n; ++i) {long long nextG = lcm(g, i);ans += ((n / g) - (n / nextG)) * i;g = nextG;if (g > n) {break;}}cout << ans << '\n';
}