BZOJ 2301/1101/2045 :[HAOI2011]Problem b – [莫比乌斯反演]

题目传送门

题解:

首先此题可以化成四个式子容斥的形式,基础式子便是
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)=\;\;d]
推导过程如下 :
默认n<m

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)=\;\;d]

\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i, j)=\;\;1]

\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p\mid (i, j)}\mu(p)

\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor

然后就可以预处理莫比乌斯函数的前缀和,再对后面的\sqrt{N}求和了

代码:

#include 
#include 
#include 
#include 
const int N = 51000;
bool np[N];
int pr[N], tot, mu[N],  sum[N];
using namespace std;
void init() {
    mu[1]=1;
    sum[1]=1;
    for(int i=2;ib)swap(a,b);
    int lst = 0;
    long long ans=0;
    for(int p=1;p<=a;p=lst+1) {
        lst=min(a/(a/p),b/(b/p));
        ans+=(long long)(sum[lst]-sum[p-1])*(a/p)*(b/p);
    }
    return ans;
}
int main() {
    int t,a,b,c, d, k;
    init();
    //for(int i=1;i<=50000;i++) printf("%d\n",sum[i]);
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d%d",&a,&b,&c, &d, &k);
        a--, c--;
        long long ans1 = work(b,d,k);
        ans1-= work(a, d, k);
        ans1-= work(b, c, k);
        ans1+= work(a, c, k);
        printf("%lld\n", ans1);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注