【LuoguP3312】[SDOI2014]数表

题目链接

题目描述

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

题解

假设没有a的限制

每次是求：

∑ni=1∑mj=1∑d|gcd(i,j)d ∑ i = 1 n ∑ j = 1 m ∑ d | g c d ( i , j ) d 枚举d

=∑min(n,m)d=1d∗nd∗md = ∑ d = 1 m i n ( n , m ) d ∗ n d ∗ m d

是不是化的太快了，好像没什么用。加上a的限制就不会做了。

看一下原来每个位置的数是gcd(i,j)的约数和。 设F(x)表示x的约数和 设 F ( x ) 表 示 x 的 约 数 和

那么要求的是:

∑ni=1∑mj=1F(gcd(i,j)) ∑ i = 1 n ∑ j = 1 m F ( g c d ( i , j ) )

=∑min(n,m)dF(d)∑ndi=1∑mdj=1[gcd(i,j)=1] = ∑ d m i n ( n , m ) F ( d ) ∑ i = 1 n d ∑ j = 1 m d [ g c d ( i , j ) = 1 ]

=∑min(n,m)dF(d)∑min(nd,md)p=1μ(p)npd∗mpd = ∑ d m i n ( n , m ) F ( d ) ∑ p = 1 m i n ( n d , m d ) μ ( p ) n p d ∗ m p d

=∑min(n,m)T=1nT∗mT∑d|Tμ(Td)F(d) = ∑ T = 1 m i n ( n , m ) n T ∗ m T ∑ d | T μ ( T d ) F ( d )

P.S:你有没有发现 ∑d|Tμ(Td)F(d)=d ∑ d | T μ ( T d ) F ( d ) = d

这下有a的限制也好办了，我们不就是要快速搞一个后面那一坨的和嘛，有a的限制的话，把a排序，把F(d)按顺序插到一个树状数组里就可以了。

F(x)可以线性筛。 F ( x ) 可 以 线 性 筛 。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=+;
typedef long long ll;
const ll mod=(l<<);
inline int read()
{
    int x=;char ch=getchar();int t=;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<)+(x<<)+(ch-);
    return x*t;
}
inline ll readl()
{
    ll x=;char ch=getchar();ll t=;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<)+(x<<)+(ch-);
    return x*t;
}
int pri[N];int cnt=;
int mu[N];
int c[N];//某数的质因子中当前最小的次数的幂
int g[N];//某数的质因子中当前最小的次数的数的幂的和
int sum[N];//某数的约数个数和
bool vis[N];
int id[N];
//若n=p1^a1 p2^a2 p3^a3...pn^an
//那么因为质因子是从小到大来枚举的,那么可以保证每次往数中添加的是最小的质因子
inline void prepare(int MAXN)
{
    mu[]=;vis[]=;id[]=;sum[]=;
    for(register int i=;i<=MAXN;++i)
    {
        id[i]=i;
        if(!vis[i]) {pri[++cnt]=i;mu[i]=-;c[i]=i;g[i]=+i;sum[i]=i+;}
        for(register int j=;j<=cnt&&(l*i*pri[j]<=MAXN);++j)
        {
            register int x=i*pri[j];
            vis[x]=;
            if(i%pri[j]==){
                mu[x]=;c[x]=c[i]*pri[j];
                g[x]=g[i]+c[x];
                sum[x]=(sum[i]/g[i])*g[x];
                break;
            }
            mu[x]=-mu[i];c[x]=pri[j];
            g[x]=pri[j]+;
            sum[x]=sum[i]*g[x];
        }
    }
}
struct que{
    int n;int m;ll a;int id;
    inline bool operator <(que b)const{
        return a<b.a;
    }
}Q[];
int ans[];
inline bool cmp(int a,int b){return sum[a]<sum[b];}//按sum排序
int tr[N];int mn;
#define lowbit(a) ((a)&(-a))
inline void insert(int p,int x){while(p<=mn) {tr[p]+=x;p+=lowbit(p);}}
inline int Query(int p){int res=;while(p){res+=tr[p];p-=lowbit(p);}return res;}
inline int solve(int n,int m)
{
    register int lst=;register int l,r;
    register int res=;
    for(l=;l<=n;l=r+)
    {
        r=min(n/(n/l),m/(m/l));
        register int now=Query(r);
        res+=(n/l)*(m/l)*(now-lst);
        lst=now;
    }
    return res;
}
int main()
{
    int T=read();register int n,m;register ll a;
    for(register int i=;i<=T;++i) {
        n=read(),m=read(),a=readl();if(n>m) swap(n,m);
        Q[i]=(que){n,m,a,i};mn=max(mn,n);
    }
    prepare(mn);
    sort(Q+,Q++T);sort(id+,id++mn,cmp);
    register int h=;
    for(register int i=;i<=T;i++){
        for(;h<=mn&&sum[id[h]]<=Q[i].a;h++) {
            for(register int k=id[h];k<=mn;k+=id[h])
                if(mu[k/id[h]]) insert(k,sum[id[h]]*mu[k/id[h]]);
        }
        ans[Q[i].id]=solve(Q[i].n,Q[i].m);
    }
    for(register int i=;i<=T;i++)
    {
        if(ans[i]<) ans[i]+=,ans[i]++;
        printf("%d\n",ans[i]);
    }
}