zcmimi's blog
avatar
zc
2020-03-14 20:35:00
  • 本文总阅读量
查看原题

点击跳转

n<m,\sigma(d)d的约数和

先不考虑\sigma(\gcd(i,j))\le a

\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j)) \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d] \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} [\gcd(i,j)=1] \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sigma(d) \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor} \mu(x) {\left \lfloor \frac n{dx} \right \rfloor}{\left \lfloor \frac m{dx} \right \rfloor}

T=dx

=\sum_{T=1}^n {\left \lfloor \frac nT \right \rfloor}{\left \lfloor \frac mT \right \rfloor}\sum_{d|T}\sigma(d) \mu(\left \lfloor \frac Td \right \rfloor)

考虑a的限制

g(T)=\sum_{d|T}\sigma(d) \mu(\left \lfloor \frac Td \right \rfloor)

可以发现当d\ge a的时候才会产生贡献

将询问按a排序

每次询问的时候,按倍数枚举找到所有新的可以产生贡献的T,

动态修改g(T),可以选择树状数组这种又短常数又小的好东西

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=100000;
struct que{int n,m,a,id;bool operator<(que t)const{return a<t.a;}}q[20001];
struct bit{
    int s[N+11];
    il void add(int x,int v){for(int i=x;i<=N;i+=i&-i)s[i]+=v;}
    il int ask(int x){int ans=0;for(int i=x;i;i-=i&-i)ans+=s[i];return ans;}
    il int ask(int l,int r){return ask(r)-ask(l-1);}
}S;
int T,mu[N+11],g[N+11],pri[N],cnt=0,ANS[N];
bool b[N+11];
il int min(int x,int y){return x<y?x:y;}
pair<int,int>f[N+11];
il int sum(int n,int m){
    int ans=0;
    for(int l=1,r;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
    }
    return ans;
}
int main(){
    mu[1]=1;f[1]=make_pair(1,1);
    for(int i=2;i<=N;++i){
        if(!b[i])pri[++cnt]=i,mu[i]=-1,g[i]=i+1,f[i]=make_pair(i+1,i);
        for(int j=1;j<=cnt&&pri[j]*i<=N;++j){
            b[i*pri[j]]=1;
            if(i%pri[j]){
                mu[i*pri[j]]=-mu[i];
                g[i*pri[j]]=pri[j]+1;
                f[i*pri[j]]=make_pair(f[i].first*f[pri[j]].first,i*pri[j]);
            }
            else{
                g[i*pri[j]]=g[i]*pri[j]+1;
                f[i*pri[j]]=make_pair(f[i].first/g[i]*g[i*pri[j]],i*pri[j]);
                break;
            }
        }
    }
    sort(f+1,f+N+1);
    in(T);
    for(int i=1;i<=T;++i)in(q[i].n,q[i].m,q[i].a),q[i].id=i;
    sort(q+1,q+T+1);
    for(int t=1,j=1;t<=T;++t){
        int n=q[t].n,m=q[t].m,a=q[t].a,&ans=ANS[q[t].id];
        if(n>m)n^=m,m^=n,n^=m;
        for(;f[j].first<=a&&j<=N;++j)
            for(int k=f[j].second;k<=N;k+=f[j].second)
                S.add(k,f[j].first*mu[k/f[j].second]);
        for(int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans+=S.ask(l,r)*(n/l)*(m/l);
        }
    }
    for(int i=1;i<=T;++i)out(ANS[i]&(~(1<<31)),ln);
    flush();
}
LG 3312 [SDOI2014]数表
comment评论
Search
search