【题目描述】
给出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; }
没有帐号? 立即注册