【SDOI2014】數表

Description

求

∑i=1n∑j=1mf(gcd(i,j))[f(gcd(i,j))≤a]

其中 f(n)=∑d|nd

Q 組資料，每組資料給出n,m,a

1≤n,m≤105,1≤Q≤2∗104

Analysis

預設 n≤m

顯然 f 可以nlogn預處理

先考慮單次詢問

反演可得

Ans=∑d=1nf[d]∑i=1⌊n/d⌋⌊ndi⌋⌊mdi⌋μ[i]

這樣就有60分了

接着套路，設 T=di

∑T=1n⌊nT⌋⌊mT⌋∑d|Tf(d)μ(T/d)

後面部分隻與 T 相關，設為g(T)，則

∑T=1n⌊nT⌋⌊mT⌋g(T)

單次詢問可以分塊，做到 O(n√)

但是這個 g(T) 會變，因為要滿足 f(d)≤a 的 d 才能算進g裡面

是以我們可以離線，将所有詢問按 a 從小到大排序

那麼對于某個d，如果滿足了小于 a 就要更新所有的g(d∗i)

如果我們用樹狀數組維護字首和，那麼就暴力枚舉倍數更新就好了

更新總複雜度複雜度 O(nlog2n)

然後分塊的時候就可以在樹狀數組裡面查詢，單次查詢複雜度 O(n√logn)

注意本題需要卡常技巧

Code

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=,MX=;
const ll mo=;
int f[N],mu[N],pri[N],an[N],tr[N];
struct op
{
    int n,m,k,id;
}b[N];
struct lyd
{
    int x,id;
}a[N];
bool bz[N+];
bool cmp(op a,op b)
{
    return a.k<b.k;
}
bool cmpa(lyd a,lyd b)
{
    return a.x<b.x;
}
void pre()
{
    mu[]=;
    fo(i,,MX)
    {
        if(!bz[i]) pri[++pri[]]=i,mu[i]=-;
        fo(j,,pri[])
        {
            ll x=i*pri[j];
            if(x>MX) break;
            bz[x]=;
            if(i%pri[j]==)
            {
                mu[x]=;
                break;
            }
            mu[x]=-mu[i];
        }
    }
}
int lowbit(int x)
{
    return x&-x;
}
int get(int x)
{
    int t=;
    for(int i=x;i;i-=lowbit(i)) t=((ll)t+tr[i])%mo;
    return t;
}
void add(int x,int y)
{
    y=((ll)y+mo)%mo;
    for(int i=x;i<=MX;i+=lowbit(i)) tr[i]=((ll)tr[i]+y)%mo;
}
int main()
{
    freopen("table.in","r",stdin);
    freopen("table.out","w",stdout);
    fo(i,,MX)
        for(int j=i;j<=MX;j+=i) (f[j]+=i)%=mo;
    fo(i,,MX) a[i].x=f[i],a[i].id=i;
    sort(a+,a+MX+,cmpa);
    pre();
    int T;
    scanf("%d",&T);
    fo(i,,T) scanf("%d %d %d",&b[i].n,&b[i].m,&b[i].k),b[i].id=i;
    sort(b+,b+T+,cmp);
    int p=;
    fo(l,,T)
    {
        int n=b[l].n,m=b[l].m;
        if(n>m) swap(n,m);
        for(;a[p].x<=b[l].k && p<=MX;p++)
        {
            int t=a[p].id;
            for(int j=t;j<=MX;j+=t) add(j,a[p].x*mu[j/t]);
        }
        ll ans=;
        int lst=;
        for(int i=,j;i<=n;i=j+)
        {
            j=min(n/(n/i),m/(m/i));
            int s=get(j);
            ll t=(s-lst+mo)%mo;
            lst=s;
            ans=(ans+(n/i)*(m/i)*t%mo)%mo;
        }
        an[b[l].id]=ans;
    }
    fo(i,,T) printf("%d\n",an[i]);
    return ;
}