【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]);
    }
}