\(\mathcal{Description}\)

令 \(\sigma(n)\) 为 \(n\) 的约数之和。求：

\[\sum_{i=1}^n\sum_{j=1}^n\max\{i,j\}\sigma(ij)\bmod(10^9+7)
\]

多测，\(n\le10^6\)，数据组数 \(\le5\times10^4\)。

\(\mathcal{Solution}\)

直接来 owo！

\[\sum_{i=1}^n\sum_{j=1}^n\max\{i,j\}\sigma(ij)=2\sum_{i=1}^ni\sum_{j=1}^i\sigma(ij)-\sum_{i=1}^ni\sigma(i^2)
\]

先研究一下 \(\sigma(ij)\)。考虑分别枚举 \(i\) 的约数 \(x\) 和 \(j\) 的约数 \(y\)，若 \(x\perp\frac{j}y\)，则对 \(\sigma(ij)\) 贡献一个 \(xy\)，显然贡献不重不漏。即：

\[\sigma(ij)=\sum_{x|i}\sum_{y|j}xy[x\perp\frac{j}y]
\]

考虑原式前一项，记 \(f(n)=n\sum_{i=1}^n\sigma(ni)\)，有：

\[\begin{aligned}
f(n)&=n\sum_{i=1}^n\sum_{x|n}\sum_{y|i}xy[x\perp\frac{i}y]\\
&=n\sum_{i=1}^n\sum_{x|n}\sum_{y|i}xy\sum_{d|x\land d|\frac{i}y}\mu(d)\\
&=n\sum_{i=1}^n\sum_{d|n\land d|i}\mu(d)\sum_{x|n\land d|x}\sum_{y|i\land d|y}\frac{ix}y\\
&=n\sum_{i=1}^n\sum_{d|n\land d|i}\mu(d)\sum_{x|\frac{n}d}\sum_{y|\frac{i}d}\frac{ix}y~~~~~~~~(x,y\mbox{ 同时约掉 } d)\\
&=n\sum_{i=1}^n\sum_{d|n\land d|i}\mu(d)\sigma(\frac{n}d)\sum_{y|\frac{i}d}\frac{i}y\\
&=n\sum_{i=1}^n\sum_{d|n\land d|i}\mu(d)\sigma(\frac{n}d)d\sum_{y|\frac{i}d}\frac{\frac{i}y}d\\
&=n\sum_{i=1}^n\sum_{d|n\land d|i}d\mu(d)\sigma(\frac{n}d)\sigma(\frac{i}d)\\
&=n\sum_{d|n}d\mu(d)\sigma(\frac{n}d)\sum_{i=1}^\frac{n}{d}\sigma(i)
\end{aligned}
\]

筛出 \(\mu,\sigma\)，枚举 \(d\) 和 \(\frac{n}d\)，可以 \(\mathcal O(n\ln n)\) 算出所有 \(f\)。

后一项呢，就是要筛 \(\sigma(n^2)\)。和筛 \(\sigma(n)\) 类似，记录一下当前最小素因子的等比数列求和，就可以 \(\mathcal O(n)\) 算出来。

综上，复杂度 \(\mathcal O(n\ln n+T)\)。

\(\mathcal{Code}\)

/* Clearink */

#include <cstdio>

typedef long long LL;

inline int rint () {

	int x = 0, f = 1; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x * f;

}

const int MAXN = 1e6, MOD = 1e9 + 7;

int pn, pr[MAXN + 5], mpwr[MAXN + 5], mu[MAXN + 5], sig[MAXN + 5], sigs[MAXN + 5];

int f[MAXN + 5], ans[MAXN + 5];

LL dpwr[MAXN + 5], g[MAXN + 5];

bool vis[MAXN + 5];

inline void init ( const int n ) {

	mu[1] = sig[1] = sigs[1] = g[1] = 1;

	for ( int i = 2; i <= n; ++ i ) {

		if ( !vis[i] ) {

			mu[pr[++ pn] = i] = -1;

			sig[i] = mpwr[i] = i + 1;

			dpwr[i] = g[i] = 1ll * i * i + i + 1;

		}

		for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= n; ++ j ) {

			vis[t] = true;

			if ( !( i % pr[j] ) ) {

				mpwr[t] = mpwr[i] * pr[j] + 1;

				dpwr[t] = dpwr[i] * pr[j] * pr[j] + pr[j] + 1;

				sig[t] = sig[i] / mpwr[i] * mpwr[t];

				g[t] = g[i] / dpwr[i] * dpwr[t];

				break;

			}

			mu[t] = -mu[i];

			mpwr[t] = mpwr[pr[j]];

			dpwr[t] = dpwr[pr[j]];

			sig[t] = sig[i] * sig[pr[j]];

			g[t] = g[i] * g[pr[j]];

		}

		sigs[i] = ( sigs[i - 1] + sig[i] ) % MOD;

	}

	for ( int i = 1; i <= n; ++ i ) g[i] = i * g[i] % MOD;

	for ( int i = 1; i <= n; ++ i ) {

		for ( int j = 1, t = n / i; j <= t; ++ j ) {

			f[i * j] = ( f[i * j] + 1ll * i * mu[i] * sig[j] % MOD * sigs[j] ) % MOD;

		}

	}

	for ( int i = 1; i <= n; ++ i ) {

		f[i] = 1ll * i * ( f[i] + MOD ) % MOD;

		ans[i] = ( ( ans[i - 1] + 2ll * f[i] - g[i] ) % MOD + MOD ) % MOD;

	}

}

int main () {

	init ( MAXN );

	for ( int T = rint (), i = 1; i <= T; ++ i ) {

		printf ( "Case #%d: %d\n", i, ans[rint ()] );

	}

	return 0;

}

\(\mathcal{Details}\)

突然觉得推式子好养生啊。（

巴特西

Solution -「51nod 1584」加权约数和

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章