题解 P3312 【[SDOI2014]数表】

· · 题解

令g(k)=\sum\limits_{i=1}^n \sum\limits_{j=1}^m gcd(i,j)==k

g(k)=\sum\limits_{i|d} \mu(\frac{d}{i})\cdot \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor

那么 \sum\limits_{i=1}^n \sum\limits_{j=1}^m F(gcd(i,j))

=\sum\limits_{i=1}^n F(i)g(i) =\sum\limits_{i=1}^n F(i) \sum\limits_{i|d} \mu(\frac{d}{i})\cdot \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor =\sum\limits_{e=1}^n \lfloor \frac{n}{e} \rfloor \lfloor \frac{m}{e} \rfloor \sum\limits_{i|e} F(i)\cdot \mu (\frac{e}{i})

如果我们预处理 \xi (e) = \sum\limits_{i|e} F(i)\cdot \mu (\frac{e}{i})

就可以在O(q\sqrt{n})时间内求出答案.

现在考虑a的限制.

注意到所有F(i)<a的i会对答案产生贡献.

故将操作离线,对询问按a升序排序,对F(i)按i排序.

每次将所有满足要求的函数值插入"某个数据结构"中,该数据结构需支持单点修改和区间求和.

那当然是常数小又好写的BIT啦.

模数的特殊性质:

可以直接爆int取模.

蒟蒻的代码:


#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<ctime>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 520010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define db double
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}

int pri[size],mu[size+10],pnt;
bool isp[size+10];

void euler()
{
    mu[1]=1; isp[1]=1;
    rep(i,2,size)
    {
        if (!isp[i]) pri[++pnt]=i,mu[i]=-1;
        rep(j,1,pnt)
        {
            if (i*pri[j]>size) break;
            isp[i*pri[j]]=1;
            if (i%pri[j])
                mu[i*pri[j]]=-mu[i];
                    else
                    {
                        mu[i*pri[j]]=0; break;
                    }
        }
    }

}

struct qwq
{
    int n,m,a,id;
}q[20010];

bool cmp(qwq A,qwq B)
{
    return (A.a<B.a);
}

struct sigma
{
    int id,dat;
}seq[size];

bool cmp1(sigma S,sigma T)
{
    return (S.dat<T.dat);
}

int c[size],ans[size],T;
#define lb(x) x&(-x)

void add(int i,int x)
{
    for (;i<=100000;i+=lb(i)) c[i]+=x;
}

int query(int x)
{
    int ans=0; for (int i=x;i;i-=lb(i)) ans+=c[i]; return ans;
}

int calc(int n,int m)
{
    int ans=0;
    if (n>m) swap(n,m);
    for (int now=1,nxt;now<=n;now=nxt+1)
    {
        nxt=min(n/(n/now),(m/(m/now)));
        ans+=(n/now)*(m/now)*(query(nxt)-query(now-1));
    }
    return ans;
}

int main()
{
    euler();
    T=r();
    for (int i=1;i<=100000;i++)
    {
        seq[i].id=i;
        for (int j=1;j*i<=100000;j++) seq[i*j].dat+=i;
    }
    sort(seq+1,seq+100000+1,cmp1);
    for (int i=1;i<=T;i++) {scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a);q[i].id=i;}
    sort(q+1,q+T+1,cmp);
    memset(c,0,sizeof(c));
    int tmp=0;
    for (int i=1;i<=T;i++)
    {
        while (tmp<100000 && seq[tmp+1].dat<=q[i].a)
        {
            tmp++;
            for (int j=1;j*seq[tmp].id<=100000;j++) add(j*seq[tmp].id,mu[j]*seq[tmp].dat);
        }   
        ans[q[i].id]=calc(q[i].n,q[i].m);
    }
    for (int i=1;i<=T;i++) printf("%d\n",ans[i]&0x7fffffff);
    return 0;
}