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

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

[egin{aligned} &sum_{i=a}^bfrac{ib}{(i,b)}\ =&bsum_{i=a}^bfrac i{(i,b)}\ =&bsum_{d|b}sum_{i=a}^b[d|i]left[left(frac id,frac bd ight)=1 ight]frac id\ =&bsum_{d|b}sum_{i=leftlceilfrac ad ight ceil}^{frac bd}left[left(i,frac bd ight)=1 ight]i\ =&bsum_{d|b}sum_{i=leftlceilfrac ad ight ceil}^{frac bd}isum_{d'|i,d'|frac bd}mu(d')\ =&bsum_{d|b}sum_{d'|frac bd}mu(d')sum_{i=leftlceilfrac {a}{dd'} ight ceil}^{frac{b}{dd'}}id'\ =&bsum_{T|b}sum_{d|T}mu(d)sum_{i=leftlceilfrac aT ight ceil}^{frac bT}id\ =&bsum_{T|b}frac{left(leftlceilfrac aT ight ceil+frac bT ight)left(frac bT-leftlceilfrac aT ight ceil+1 ight)}{2}sum_{d|T}mu(d)d end{aligned} ]

(sumlimits_{d|T}mu(d)d=prodleft(1-p_i ight))，只要确定T的质因子就可以确定(sumlimits_{d|T}mu(d)d)的值。
如果循环枚举T找b的约数，无法快速计算T的质因子。
可以dfs枚举b的约数T，动态计算(sumlimits_{d|T}mu(d)d)的值。
时间复杂度(Oleft(Tsqrt n ight))。

#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
", 1ll * b * ans % p);
	}
	
	return 0;
}