LOJ 124 & 125 除数函数求和

除数函数求和1

题目

\(\sigma-k(n)=\sum_{d\mid n}d^k\)
求\(\sum_{i=1}^{n}\sigma-k(i)\)的值对\(1e9+7\)取模的结果。
### 题解 直接枚举约数
\(\sum\limits_{d=1}^{n}d^k\sum\limits_{i=1}^{n}[d\mid i]\)
\(\sum\limits_{d=1}^{n}d^k\left\lfloor\frac{n}{d}\right\rfloor\)
欧拉筛预处理\(d^k\)，数论分块即可。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e7 + 5, MOD = 1e9  + 7;
int P[N], n, k, cnt, mi[N], vis[N];

int fpow(int a, int b) {
    int res = 1;
	for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) res = res * 1ll * a % MOD;
	return res;
}
void init(int n) {
	mi[0] = 0, mi[1] = 1;
    for (int i = 2; i <= n; i++) {
    	if (!vis[i]) P[++cnt] = i, mi[i] = fpow(i, k);
    	for (int j = 1; j <= cnt && P[j] * i <= n; j++) {
    		vis[i * P[j]] = 1;
    		mi[i * P[j]] = mi[i] * 1ll * mi[P[j]] % MOD;
    		if (i % P[j] == 0) break;
    	}
    }
    for (int i = 1; i <= n; i++) mi[i] = ((ll)mi[i] + (ll)mi[i - 1]) % MOD;
}

int main() {
    scanf("%d %d", &n, &k);
    init(n);
    int res = 0;
    for (int i = 1, j; i <= n; i = j + 1) {
    	j = n / (n / i);
        res = ((ll)res + (n / i) * 1ll * (mi[j] - mi[i - 1]) % MOD + MOD) % MOD; 
    }
    printf("%d\n", res);
    return 0;
}

除数函数求和2

###题目 求\(\sum_{i=1}^{n}2\sigma-2(i)+3\sigma-1(i)+5\sigma-0(i)\)对\(998244353\)取模。
其中\(\sigma-k(n)=\sum_{d\mid n}d^k\)。

###题解 先把式子展开，有前面的经验，将三个式子分开计算。
\(2\sum_{i=1}^{n}\sigma-2(i)+3\sum_{i=1}^{n}\sigma-1(i)+5\sum_{i=1}^{n}\sigma-0(i)\)
\(2\sum_{d=1}^{n}d^2\left\lfloor\frac{n}{d}\right\rfloor+3\sum_{i=1}^{n}d\left\lfloor\frac{n}{d}\right\rfloor+5\sum_{i=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor\)
第三个显然数论分块。
前两个结合一下自然数幂之和的公式。
\(\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}\)
\(\sum\limits_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353, i6 = 166374059, i2 = 499122177;
int n;

int qry1(int x, int y) {
	return (((y + 1) * 1ll * y % MOD) * i2 % MOD - ((x + 1) * 1ll * x % MOD) * i2 % MOD) % MOD;  
}
int qry2(int x, int y) {
	return ((y * 1ll * (y + 1) % MOD * (2 * y + 1) % MOD) * i6 % MOD - (x * 1ll * (x + 1) % MOD * (2 * x + 1) % MOD) * i6 % MOD) % MOD;
}

int main() {
    scanf("%d", &n);
    int res0 = 0, res1 = 0, res2 = 0;
    for (int i = 1, j; i <= n; i = j + 1) {
    	j = n / (n / i);
    	res0 = ((ll)res0 + (j - i + 1) * 1ll * (n / i)) % MOD;
    }
    for (int i = 1, j; i <= n; i = j + 1) {
    	j = n / (n / i);
    	res1 = (res1 + qry1(i - 1, j) * 1ll * (n / i) % MOD) % MOD;
    }
    for (int i = 1, j; i <= n; i = j + 1) {
    	j = n / (n / i);
    	res2 = (res2 + qry2(i - 1, j) * 1ll * (n / i) % MOD) % MOD;
    }
    printf("%lld\n", ((2 * 1ll * res2 % MOD + 3 * 1ll * res1 % MOD + 5 * 1ll * res0 % MOD) % MOD + MOD) % MOD);
    return 0;
}