M_sea

洛谷3312 [SDOI2014]数表
LuoguBZOJ分析以下内容中默认 $n<m$ 。我们先假装没看到那个 $a$ 的限制。那么就是要求 $\...
扫描右侧二维码阅读全文
28
2019/03

洛谷3312 [SDOI2014]数表

Luogu

BZOJ

分析

以下内容中默认 $n<m$ 。

我们先假装没看到那个 $a$ 的限制。

那么就是要求 $\large\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma\big(\gcd(i,j)\big)$ 。

枚举 $\gcd$ :$\large\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma(d)[\gcd(i,j)=d]$

进一步得到 $\large\sum\limits_{d=1}^n\sigma(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}[\gcd(i,j)=1]$

后面反演得到 $\large\sum\limits_{d=1}^n\sigma(d)\sum\limits_{i=1}^{n/d}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor$

设 $T=id$ ,提出来得到 $\large\sum\limits_{T=1}^n\sum\limits_{d|T}\sigma(d)\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$

换下顺序得到 $\large\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}\sigma(d)\mu(\frac{T}{d})$

那么直接筛出后面的东西,然后数论分块算就行了。


然而有 $a$ 的限制,所以忽略上面的那句话。

发现,只有 $\sigma(d)\leq a$ 的 $d$ 才有贡献。

那么将所有询问离线按 $a$ 排序,然后把所有数按 $\sigma$ 的值排序,一个一个加进去即可。

用一个树状数组来维护 $g(T)=\sum\limits_{d|T}\sigma(d)\mu(\frac{T}{d})$ 即可。

至于怎么取膜,可以用 $\mathrm{int}$ 的自然溢出。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int p[N],v[N],tot;
int mu[N],sig[N],sumd[N],powd[N];

inline void sieve(int n) {
    v[1]=sig[1]=mu[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++tot]=i,mu[i]=-1,sig[i]=i+1,sumd[i]=i+1,powd[i]=i;
        for (re int j=1;j<=tot&&i*p[j]<=n;++j) {
            v[i*p[j]]=1; int t=i*p[j];
            if (i%p[j]) {
                mu[t]=-mu[i],sig[t]=sig[i]*sig[p[j]];
                sumd[t]=p[j]+1,powd[t]=p[j];
            } else {
                powd[t]=powd[i]*p[j],sumd[t]=sumd[i]+powd[t];
                sig[t]=sig[i]/sumd[i]*sumd[t];
                break;
            }
        }
    }
}

int mx,a[N],ans[N];
struct query { int n,m,a,id; } q[N];
bool operator <(query a,query b) { return a.a<b.a; }
inline int cmp(int a,int b) { return sig[a]<sig[b]; }

int c[N];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    for (;x<=mx;x+=lowbit(x)) c[x]+=y;
}
inline int sum(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

inline int calc(int n,int m) {
    int ans=0;
    for (re int l=1,r;l<=n;l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=(sum(r)-sum(l-1))*(n/l)*(m/l);
    }
    return ans;
}

int main() {
    int T=read(); mx=0; sieve(1e5);
    for (re int i=1;i<=T;++i) {
        q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i;
        if (q[i].n>q[i].m) swap(q[i].n,q[i].m);
        mx=max(mx,q[i].m);
    }
    sort(q+1,q+T+1);
    for (re int i=1;i<=mx;++i) a[i]=i;
    sort(a+1,a+mx+1,cmp);
    for (re int i=1,j=1;i<=T;++i) {
        while (j<=mx&&sig[a[j]]<=q[i].a) {
            for (re int k=a[j];k<=mx;k+=a[j])
                if (mu[k/a[j]]) add(k,sig[a[j]]*mu[k/a[j]]);
            ++j;
        }
        ans[q[i].id]=calc(q[i].n,q[i].m);
    }
    for (re int i=1;i<=T;++i) {
        if (ans[i]<0) ans[i]+=2147483647,++ans[i];
        printf("%d\n",ans[i]);
    }
    return 0;
}
最后修改:2019 年 03 月 28 日 08 : 11 PM

发表评论