BZOJ 2693: jzptab [莫比乌斯反演 线性筛]

2693: jzptab

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 1194  Solved: 455
[Submit][Status][Discuss]

Description

Input

一个正整数T表示数据组数

接下来T行 每行两个正整数 表示N、M

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

1

4 5

Sample Output

122
HINT
T <= 10000
N, M<=10000000

---

和上题一样，不过多组数据

利用了和bzoj2820类似的技巧D=di 改变求和指标，这样就可以把Sum提前，剩下的部分处理前缀和

 

如何处理前缀和：

积性函数的约数和也是积性函数，可以用线性筛

g[i]=约数和D*i*mu[i]

显然g[p]=p*(1-p)

g[i*p[j]] 当p[j]|i时  mu[ii]中ii带有p[j]的话就是0了不能计入，所以p[j]只能在剩下的一块里，也就是只有D变了，所以总的就是p[j]*g[i]

 

尝试了一下枚举倍数的方法，T了

 

总结：其实这两道题和gcd=k的个数两道题很像，都是第一题只要求一个，第二题要求多个，然后就要改写式子然后处理前缀和......

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1e7+,MOD=;

inline int read() {

    char c=getchar();

    int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m;

bool notp[N];int p[N];

ll s[N],mu[N],g[N];

void sieve(){

    mu[]=;

    g[]=;

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

        if(!notp[i]) p[++p[]]=i,mu[i]=-,g[i]=i-(ll)i*i;

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

            int t=i*p[j];

            notp[t]=;

            if(i%p[j]==){

                mu[t]=;

                g[t]=(g[i]*p[j])%MOD;

                break;

            }

            mu[t]=-mu[i];

            g[t]=(g[i]*g[p[j]])%MOD;

        }

    }

    for(int i=;i<N;i++) g[i]=(g[i]+g[i-])%MOD;

}

inline ll S(ll x,ll y){

    return ((x*(x+)/)%MOD)*((y*(y+)/)%MOD)%MOD;

}

int main(){

    sieve();

    int T=read();

    while(T--){

        n=read();

        m=read();

        if(n>m) swap(n,m);

        ll ans=,r=;

        for(ll D=;D<=n;D=r+){

            r=min(n/(n/D),m/(m/D));

            ans=(ans+S(n/D,m/D)*(g[r]-g[D-]))%MOD;

        }

        printf("%lld\n",(ans+MOD)%MOD);

    }

}