[bzoj3529] [洛谷P3312] [Sdoi2014] 数表

Description###

有一张n×m的数表，其第i行第j列（1 < =i < =n，1 < =j < =m）的数值为

能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

Input###

输入包含多组数据。

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

Output###

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

Sample Input###

4 4 3

10 10 5

Sample Output###

148

HINT###

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

想法##

orz PoPoQQQ……

基本想法同“YY的GCD”

线性筛可筛出每个数i的约数和s[i]

之后离线处理，将a与s[]分别从小到大排序处理，莫比乌斯反演，树状数组维护前缀和。

代码##

注意：诡异的取模需要注意一下。

#include<cstdio>

#include<iostream>

#include<algorithm>

#define P 1<<31

using namespace std;

typedef long long ll;

const int N = 100005;

int mu[N];

ll s[N],sm[N];

int p[N],prime[N],pnum;

void getmu(){

    mu[1]=s[1]=1;

    for(int i=2;i<N;i++) p[i]=1;

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

        if(p[i]){

            prime[pnum++]=i;

            mu[i]=-1;

            s[i]=sm[i]=1+i;

        }

        for(int j=0;j<pnum && (ll)prime[j]*i<N;j++){

            int id=prime[j]*i;

            p[id]=0;

            if(i%prime[j]==0){

                mu[id]=0;

                s[id]=s[i]/sm[i]*(sm[i]*prime[j]+1);

                sm[id]=sm[i]*prime[j]+1;

                break;

            }

            mu[id]=-mu[i];

            s[id]=s[i]*(1+prime[j]);

            sm[id]=1+prime[j];

        }

    }

}

int num[N];

bool cmp(int x,int y) { return s[x]<s[y]; }

struct Bit{

    ll c[N];

    int lowbit(int x) { return x&(-x); }

    void add(int x,ll y){

        while(x<N){

            (c[x]+=y)%=P;

            x+=lowbit(x);

        }

    }

    ll sum(int x){

        ll ret=0;

        while(x){

            (ret+=c[x])%=P;

            x-=lowbit(x);

        }

        return ret;

    }

}f;

struct data{

    int n,m,a,id;

    bool operator < (const data &b) const{

        return a<b.a;

    }

}d[N];

ll ans[N];

int main()

{

    int T;

    getmu();

    for(int i=1;i<N;i++) num[i]=i;

    sort(num+1,num+1+100000,cmp);

    scanf("%d",&T);

    for(int i=1;i<=T;i++){

        scanf("%d%d%d",&d[i].n,&d[i].m,&d[i].a);

        d[i].id=i;

    }

    sort(d+1,d+1+T);

    int t=1,n,m;

    for(int i=1;i<=T;i++){

        while(t<N && s[num[t]]<=d[i].a) {

            for(int j=1;(ll)j*num[t]<N;j++)

                f.add(j*num[t],s[num[t]]*mu[j]);

            t++;

        }

        n=d[i].n; m=d[i].m;

        for(int l=1,r;l<=min(n,m);l=r+1){

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

            ans[d[i].id]+=(f.sum(r)-f.sum(l-1))*(n/l)*(m/l);

        }

    }

    for(int i=1;i<=T;i++)

        printf("%lld\n",ans[i]&2147483647);

    return 0;

}

巴特西