BZOJ4659:Lcm
? 解题记录 ? ? BZOJ ? ? 莫比乌斯函数 ? ? 容斥 ?    2018-08-13 11:42:45    572    0    0

【题目描述】

给出A,B,考虑所有满足l<=a<=A,l<=b<=B,且不存在n>1使得n^2同时整除a和b的有序数,对(a,b),求其lcm(a,b)之和。答案模2^30。

【输入】

第一行一个整数T表示数据组数。接下来T行每行两个整数A,B表示一组数据。

T ≤ 2000,A,B ≤ 4 × 10^6

【输出】

对每组数据输出一行一个整数表示答案模2^30的值

【输入样例】

5
2 2
4 6
3 4
5 1
23333 33333

【输出样例】

7
148
48
15
451085813​

 

 这道题网上很多题解是化出了一个函数然后快速求这个函数。这里介绍一种简单的容斥方法:考虑用总的减去不合法的,总的是一个子问题:二维LCM求和,这个题就是BZOJ2154。不合法的怎么求呢?我们发现不合法的就是含有平方因子的。然后我们考虑把他们减去:先减去含有2*2因子的,减去3*3因子的,这时含有6*6因子的就被减去了2遍,要加一遍回来……我们发现这就是平方因子开根的莫比乌斯函数。于是就可以算了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int maxn = 4e6 + 5;
const int mod = 1 << 30;
int pri[maxn], vis[maxn], mu[maxn], n, m;
int S[maxn], mukk[maxn], Smk[maxn];

int GetP(int n) {
	vis[1] = 1, mu[1] = 1, mukk[1] = 1;
	for(register int i = 2; i <= n; ++i) {
		if(!vis[i]) pri[++(*pri)] = i, mu[i] = -1, mukk[i] = 1 - i;
		for(register int j = 1; j <= *pri && pri[j] * i <= n; ++j) {
			vis[i * pri[j]] = 1;
			mu[i * pri[j]] = -mu[i];
			mukk[i * pri[j]] = mukk[i] * mukk[pri[j]];
			if(i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				mukk[i * pri[j]] = mukk[i];
				break;
			}
		}
	}
	for(register int i = 1; i <= n; ++i)
		S[i] = S[i - 1] + mu[i] * i * i, Smk[i] = mukk[i] * i + Smk[i - 1];
}

inline int Sum(int n) {return n * (n + 1) / 2;}

inline int SigLCM(const int &A, const int &B) {
	register int l = 1, r = 1;
	int mn = min(A, B);
	int ans = 0;
	for(; l <= mn; l = r + 1) {
		r = min(A / (A / l), B / (B / l));
		ans += Sum(A / l) * Sum(B / l) * (Smk[r] - Smk[l - 1]);
	}
	return ans;
}

int GetAns(const int &A, const int &B) {
	register int l = 1, r = 1;
	int ans = 0, mn = min(A, B), lsq = 1;
	for(; lsq <= mn; l = r + 1, lsq = l * l) {
		r = (int)sqrt(min(A / (A / (lsq)), B / (B / (lsq))));
		ans += (S[r] - S[l - 1]) * SigLCM(A / (lsq), B / (lsq));
	}
	return (ans + mod) % mod;
}

int t;
int main() {
	GetP(4e6);
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &m);
		printf("%d\n", (GetAns(n, m) + mod) % mod);
	}
	return 0;
}

上一篇: UOJ#317. 【NOI2017】游戏

下一篇: BZOJ2178:圆的面积并

572 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航