数表( table )

题目描述

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

输入

输入包含多组数据。

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

输出

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

样例输入

<span style="color:#333333"><span style="color:#333333">2

4 4 3

10 10 5

</span></span>

样例输出

<span style="color:#333333"><span style="color:#333333">20

148

</span></span>

提示

solution

好题，我不会

令f[i]表示i的约数的和

题目求

$\sum_{i=1}^{n} \sum_{j=1}^{m} f[gcd(i,j)]*[f[gcd(i,j)]<=a]$

gcd提出来

$\sum_{k} f[k]*[f[k]<=a] \sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i,j)==d$

反演,再把gcd提出来

$\sum_{k} f[k]*[f[k]<=a] \sum_{d}\mu(d) \sum_{i=1}^{n/kd} \sum_{j=1}^{m/kd }$

这就有60分了

但是这样子式子还是化不了

我们枚举i=k*d

$\sum_{i} \sum_{k} f[k]*[f[k]<=a] * mu(i/k) \sum_{i=1}^{n/i} \sum_{j=1}^{m/i }$

这样子就能把nm的往前提

$\sum_{i} (n/i)*(m/i) \sum_{k} f[k]*[f[k]<=a] * mu(i/k)$

把询问按a排序，按a依次加入f[k]*mu[i/k]

前面的部分可以分块，后边的前缀和起来

也就是我要支持加入和查询前缀和。

树状数组即可。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 2000006

using namespace std;

int n,Q,mu[maxn],pri[maxn],flag[maxn],sum[maxn],Max,tot;

int ans[maxn],tree[maxn];

struct node{

    int n,m,a,b,id;

}s[maxn],f[maxn];

bool cmp(node A,node B){

    return A.a<B.a;

}

void add(int i,int v){

    for(;i<=Max;i+=i&-i)tree[i]+=v;

}

int ask(int i){

    int sum=0;for(;i;i-=i&-i)sum+=tree[i];

    return sum;

}

int Query(int N,int M){

    int nex,sum=0;

    if(N>M)swap(N,M);

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

        nex=min(N/(N/i),M/(M/i));

        //if(nex<i)exit(0);

        sum+=(N/i)*(M/i)*(ask(nex)-ask(i-1));

    }

    return sum;

}

int main()

{

    n=1000000;mu[1]=1;

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

        if(!flag[i]){

            pri[++tot]=i;mu[i]=-1;

        }

        for(int j=1;j<=tot&&pri[j]<=n/i;j++){

            flag[i*pri[j]]=1;mu[i*pri[j]]=-mu[i];

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

                mu[i*pri[j]]=0;

                break;

            }

        }

    }

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

        for(int j=i;j<=n;j+=i)f[j].a+=i;

    }

    for(int i=1;i<=n;i++)f[i].b=i;

    sort(f+1,f+n+1,cmp);

    cin>>Q;

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

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

        s[i].id=i;

        if(s[i].n>s[i].m)swap(s[i].n,s[i].m);

        Max=max(Max,s[i].m);

    }

    sort(s+1,s+Q+1,cmp);

    int l=1;

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

        for(;f[l].a<=s[i].a&&l<=n;l++){

            for(int N=f[l].b;N<=Max;N+=f[l].b)

            add(N,f[l].a*mu[N/f[l].b]);

        }

        ans[s[i].id]=Query(s[i].n,s[i].m);

        if(ans[s[i].id]<0)ans[s[i].id]+=(1<<31);

    }

    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);

    return 0;

}

巴特西

数表( table )

数表( table )

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章