P3312 [SDOI2014]数表

题目描述

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

输入输出格式

输入格式：

输入包含多组数据。

输入的第一行一个整数\(Q\)表示测试点内的数据组数

接下来\(Q\)行，每行三个整数\(n\)，\(m\)，\(a\)(\(|a| \le 10^9\))描述一组数据。

输出格式：

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

说明

\(1 \le N,M\le 10^5\) ， \(1 \le Q \le 2*10^4\)

按道理就是先不管条件。

然后化简式子得到了

\[\sum_{k=1}^{\min(n,m)}k\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor
\]

想想确实不能拿掉一些东西，否则没法做。

想到有\(\mathbf {Id}=\sigma*\mu\)

于是把式子拆开

\[\sum_{k=1}^{\min(n,m)}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\sum_{d|k}\sigma(d)\mu(\frac{k}{d})
\]

或者换个方向反演也可以得到这个式子。

我们知道格子\((i,j)\)的值就是\(\sigma(gcd(i,j))\)

于是我们可以离线读入，然后从小到大把\(\sigma\)加入前缀和。

具体的，可以拿一个树状数组维护\(\sum_{d|k}\sigma(d)\mu(\frac{k}{d})\)的前缀和，然后每次查询或者加一些东西进去就可以了。

复杂度\(O(n\log^2n+Q\sqrt n\log n)\)

Code:

#include <cstdio>

#include <algorithm>

const int N=1e5;

std::pair <int,int> sigma[N+10];

int mu[N+10],v[N+10];

void init()

{

    for(int i=1;i<=N;i++) mu[i]=1,sigma[i]=std::make_pair(i+1,i);

    sigma[1].first=1;

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

    {

        if(!v[i]) mu[i]=-1;

        for(int j=i*2;j<=N;j+=i)

        {

            sigma[j].first+=i;

            if(!v[i])

            {

                if((j/i)%i==0) mu[j]=0;

                else mu[j]*=-1;

                v[j]=1;

            }

        }

    }

    std::sort(sigma+1,sigma+1+N);

}

int min(int x,int y){return x<y?x:y;}

struct node

{

    int n,m,a,id;

    bool friend operator <(node n1,node n2){return n1.a<n2.a;}

}qry[N+10];

int s[N+10],ans[N+10],pos=1,T;

void add(int p,int d){while(p<=N)s[p]+=d,p+=p&-p;}

int ask(int p){int sum=0;while(p)sum+=s[p],p-=p&-p;return sum;}

void change(int d)

{

    while(sigma[pos].first<=d&&pos<=N)

    {

        for(int i=sigma[pos].second;i<=N;i+=sigma[pos].second)

            add(i,sigma[pos].first*mu[i/sigma[pos].second]);

        ++pos;

    }

}

int main()

{

    init();

    scanf("%d",&T);

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

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

    std::sort(qry+1,qry+1+T);

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

    {

        change(qry[i].a);

        int n=qry[i].n,m=qry[i].m,sum=0;

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

        {

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

            sum+=(n/l)*(m/l)*(ask(r)-ask(l-1));

        }

        ans[qry[i].id]=sum&0x7fffffff;

    }

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

    return 0;

}

2018.11.26

巴特西

洛谷 P3312 [SDOI2014]数表解题报告

P3312 [SDOI2014]数表

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

巴特西

洛谷 P3312 [SDOI2014]数表 解题报告

P3312 [SDOI2014]数表

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

洛谷 P3312 [SDOI2014]数表解题报告