【51Nod 1190】最小公倍数之和 V2

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1190

\[\begin{aligned}
&\sum_{i=a}^b\frac{ib}{(i,b)}\\
=&b\sum_{i=a}^b\frac i{(i,b)}\\
=&b\sum_{d|b}\sum_{i=a}^b[d|i]\left[\left(\frac id,\frac bd\right)=1\right]\frac id\\
=&b\sum_{d|b}\sum_{i=\left\lceil\frac ad\right\rceil}^{\frac bd}\left[\left(i,\frac bd\right)=1\right]i\\
=&b\sum_{d|b}\sum_{i=\left\lceil\frac ad\right\rceil}^{\frac bd}i\sum_{d'|i,d'|\frac bd}\mu(d')\\
=&b\sum_{d|b}\sum_{d'|\frac bd}\mu(d')\sum_{i=\left\lceil\frac {a}{dd'}\right\rceil}^{\frac{b}{dd'}}id'\\
=&b\sum_{T|b}\sum_{d|T}\mu(d)\sum_{i=\left\lceil\frac aT\right\rceil}^{\frac bT}id\\
=&b\sum_{T|b}\frac{\left(\left\lceil\frac aT\right\rceil+\frac bT\right)\left(\frac bT-\left\lceil\frac aT\right\rceil+1\right)}{2}\sum_{d|T}\mu(d)d
\end{aligned}
\]

\(\sum\limits_{d|T}\mu(d)d=\prod\left(1-p_i\right)\)，只要确定T的质因子就可以确定\(\sum\limits_{d|T}\mu(d)d\)的值。

如果循环枚举T找b的约数，无法快速计算T的质因子。

可以dfs枚举b的约数T，动态计算\(\sum\limits_{d|T}\mu(d)d\)的值。

时间复杂度\(O\left(T\sqrt n\right)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100000;

const int p = 1000000007;

const int ni2 = 500000004;

bool notp[N];

int a, b, tot, P[N], c[N], num = 0, prime[N];

void Euler_shai() {

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

		if (!notp[i]) prime[++num] = i;

		for (int j = 1; j <= num && prime[j] * i <= N; ++j) {

			notp[prime[j] * i] = true;

			if (i % prime[j] == 0) break;

		}

	}

}

void pre(int x) {

	tot = 0;

	for (int i = 1, pi = 2; i <= num && pi * pi <= x; pi = prime[++i])

		if (x % pi == 0) {

			P[++tot] = pi; c[tot] = 0;

			while (x % pi == 0) x /= pi, ++c[tot];

		}

	if (x > 1)

		P[++tot] = x, c[tot] = 1;

}

int ans;

void dfs(int tmp, int T, int f) {

	if (tmp > tot) {

		int l = a / T, r = b / T;

		if (a % T) ++l;

		(ans += 1ll * (l + r) * (r - l + 1) % p * ni2 % p * f % p) %= p;

		return;

	}

	dfs(tmp + 1, T, f);

	int tt = T, ff = 1ll * f * (1 - P[tmp] + p) % p;

	for (int i = 1; i <= c[tmp]; ++i) {

		tt *= P[tmp];

		dfs(tmp + 1, tt, ff);

	}

}

int main() {

	Euler_shai();

	int T; scanf("%d", &T);

	while (T--) {

		scanf("%d%d", &a, &b);

		pre(b);

		ans = 0;

		dfs(1, 1, 1);

		printf("%lld\n", 1ll * b * ans % p);

	}

	return 0;

}

巴特西

【51Nod 1190】最小公倍数之和 V2

最新文章

热门文章