BZOJ 3529: [Sdoi2014]数表 [莫比乌斯反演树状数组]

3529: [Sdoi2014]数表

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 1399 Solved: 694
[Submit][Status][Discuss]

Description

有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为
能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

Input

输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

Output

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

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148

HINT

1 < =N．m < =10^5 ， 1 < =Q < =2×10^4

Source

Round 1 Day 1

一个位置的答案就是gcd(i,j)的约数和

一个个单独算不好优化不行，从gcd(i,j)的取值方面考虑，因为它的取值就是1...n

设F(i)为i的约数和，f(i)为gcd(x,y)=i的个数，那么答案就是ΣF(i)*f(i)

f(i)上两题用到过，反演后f(i)=Σ{i|d} miu(d/i)*(n/d)*(m/d)

d和i的取值范围相同，可以得到如下式子

现在我们只需要求出g(i)=的前缀和这个问题就能在O(√n)的时间内出解

F(i)是约数和函数，可以通过线性筛计算，或者直接nlogn暴力枚举倍数，速度差不多

然后和上一题一样，暴力枚举每个i更新它的倍数

那么a的限制如何处理？考虑离线

我们发现对答案有贡献的i只有F(i)<=a的i 那么我们将询问按照a从小到大排序将F(i)从小到大排序每次询问将<=a的F(i)按照枚举倍数更新的方式插入用树状数组来维护g的前缀和这样枚举倍数logn，每个倍数插入树状数组logn，总共nlog^2n

本题取模有一种好厉害的做法：自然溢出int,最后&0x7FFFFFFF

复杂度O(nlog^2n+q√nlogn)

注意:排序[1,N)的话是sort(a+1,a+N),不要a+N+1.......

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
struct ques{
    int n,m,a,id;
    bool operator <(const ques &r)const{return a<r.a;}
}q[N];
int n,m;
int notp[N],p[N],mu[N],minfac[N],t1[N],t2[N];
struct data{
    int s,i;
    bool operator <(const data &r)const{return s<r.s;}
}sf[N];
void sieve(){
    for(int i=1;i<N;i++) sf[i].i=i;
    mu[1]=1;
    sf[1].s=1;
    for(int i=2;i<N;i++){
        if(!notp[i]){
            p[++p[0]]=i,mu[i]=-1;
            minfac[i]=i;
            sf[i].s=i+1;
            t1[i]=i+1;
            t2[i]=i;
        }
        for(int j=1,k;j<=p[0]&&(k=i*p[j])<N;j++){
            notp[i*p[j]]=1;
            minfac[k]=p[j];
            if(i%p[j]==0){
                mu[i*p[j]]=0;
                t2[k]=t2[i]*p[j];
                t1[k]=t1[i]+t2[k];
                sf[k].s=sf[i].s/t1[i]*t1[k];
                break;
            }
            mu[i*p[j]]=-mu[i];
            t1[k]=1+p[j];
            t2[k]=p[j];
            sf[k].s=sf[i].s*sf[p[j]].s;
        }
    }
}

int g[N];
inline int lowbit(int x){return x&-x;}
inline void add(int p,int v){for(int i=p;i<N;i+=lowbit(i)) g[i]+=v;}
inline int sum(int p){
    int ret=0;
    for(int i=p;i;i-=lowbit(i)) ret+=g[i];
    return ret;
}
void ins(int x){
    for(int d=sf[x].i;d<N;d+=sf[x].i) add(d,sf[x].s*mu[d/sf[x].i]);
}
int cal(int n,int m){
    int ans=0,r=0;
    if(n>m) swap(n,m);
    for(int i=1;i<=n;i=r+1){
        r=min(n/(n/i),m/(m/i));
        ans+=(sum(r)-sum(i-1))*(n/i)*(m/i);
    }
    return ans;
}
int ans[N];
int main(int argc, const char * argv[]){
    sieve();
    sort(sf+1,sf+N);//!!!!!
    int T=read();
    for(int i=1;i<=T;i++) q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i;
    sort(q+1,q+1+T);
    int now=1;
    for(int i=1;i<=T;i++){
        int a=q[i].a;
        for(;sf[now].s<=a;now++) ins(now);
        ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF;
    }
    for(int i=1;i<=T;i++) printf("%d
",ans[i]);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
struct ques{
    int n,m,a,id;
    bool operator <(const ques &r)const{return a<r.a;}
}q[N];
int n,m;
int notp[N],p[N],mu[N];
struct data{
    int s,i;
    bool operator <(const data &r)const{return s<r.s;}
}sf[N];
void sieve(){
    mu[1]=1;
    for(int i=2;i<=100000;i++){
        if(!notp[i]){
            p[++p[0]]=i,mu[i]=-1;
        }
        for(int j=1,k;j<=p[0]&&(k=i*p[j])<=100000;j++){
            notp[k]=1;
            if(i%p[j]==0){
                mu[k]=0;
                break;
            }
            mu[k]=-mu[i];
        }
    }
    for(int i=1;i<=100000;i++){
        sf[i].i=i;
        for(int j=1;j*i<=100000;j++) sf[i*j].s+=i;
    }
}

int g[N];
inline int lowbit(int x){return x&-x;}
inline void add(int p,int v){for(int i=p;i<N;i+=lowbit(i)) g[i]+=v;}
inline int sum(int p){
    int ret=0;
    for(int i=p;i;i-=lowbit(i)) ret+=g[i];
    return ret;
}
inline void ins(int x){
    for(int d=sf[x].i;d<=100000;d+=sf[x].i) add(d,sf[x].s*mu[d/sf[x].i]);
}
int cal(int n,int m){
    int ans=0,r=0;
    if(n>m) swap(n,m);
    for(int i=1;i<=n;i=r+1){
        r=min(n/(n/i),m/(m/i));
        ans+=(sum(r)-sum(i-1))*(n/i)*(m/i);
    }
    return ans;
}
int ans[N];
int main(int argc, const char * argv[]){
    sieve();
    sort(sf+1,sf+100000);
    int T=read();
    for(int i=1;i<=T;i++) q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i;
    sort(q+1,q+1+T);
    int now=1;
    for(int i=1;i<=T;i++){
        int a=q[i].a;
        for(;now<=100000&&sf[now].s<=a;now++) ins(now);
        ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF;
    }
    for(int i=1;i<=T;i++) printf("%d
",ans[i]);
    return 0;
}