小G的GCD / 小G的sigma

题目链接：nowcoder 218397

到主站看：https://blog.csdn.net/weixin_43346722/article/details/114552306

题目大意

给出一个数 k，定义 F(x) 为 j=1x 中被 k 整除的 j 的和。
然后要你求 i=1n 中每个 F(i) 值的和。

思路

这道题很明显看到 函数是有前缀和的感觉的。

你就每个看新多一个数，它是否被 整除，如果整除，这个的答案就是上个加上新加的数，否则答案跟上一个一样。

那我们枚举一下，就可以求出每个 ，那求和也很简单了。

代码

#include<cstdio>
#define ll long long

using namespace std;

int n, k;
ll ans, now;

int main() {
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++) {
        if (i % k == 0) now += 1ll * i;
        ans += now;
    }

    printf("%lld", ans);

    return 0;
}