SP34096 DIVCNTK - Counting Divisors (general)(Min

题面

洛谷

\(\sigma_0(i)\) 表示\(i\) 的约数个数

求\(S_k(n)=\sum_{i=1}^n\sigma_0(i^k)\mod 2^{64}\)

多测,\(T\le10^4,n,k\le10^{10}\)

题解

令\(f(i)=\sigma_0(i^k)\)首先可以发现几个性质

\[f(1)=1
\]

\[f(p)=k+1
\]

\[f(p^c)=kc+1
\]

\[f(ab)=f(a)f(b),\gcd(a,b)=1
\]

也就是说\(f\)是个积性函数，直接上\(Min\_25\)筛就行了

然后把本题里的\(k\)改成\(2\)和\(3\)就可以水过\(DIVCNT2\)和\(DIVCNT3\)了

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll unsigned long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

ll read(){

    R ll res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R ll x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=1e5+5;

bitset<N>vis;int p[N],id1[N],id2[N],sqr,m;

ll n,k,lim,tot,w[N<<1],sp[N],g[N<<1],h[N<<1];

void init(int n){

	fp(i,2,n){

		if(!vis[i])p[++tot]=i;

		for(R int j=1;j<=tot&&1ll*i*p[j]<=n;++j){

			vis[i*p[j]]=1;

			if(i%p[j]==0)break;

		}

	}lim=tot;

}

ll S(ll x,int y){

	if(x<=1||p[y]>x)return 0;

	int id=(x<=sqr)?id1[x]:id2[n/x];

	ll res=g[id]+h[id]-(k+1)*(y-1);

	for(int i=y;i<=tot&&1ll*p[i]*p[i]<=x;++i){

		ll tmp=p[i];

		for(R int e=1;tmp*p[i]<=x;tmp*=p[i],++e){

			id=(x/tmp<=sqr)?id1[x/tmp]:id2[n/(x/tmp)];

			res+=S(x/tmp,i+1)*(k*e+1)+k*(e+1)+1;

		}

	}

	return res;

}

void solve(){

	n=read(),k=read(),sqr=sqrt(n),m=0;

	tot=upper_bound(p+1,p+1+lim,sqr)-p-1;

	for(R ll i=1,j;i<=n;i=j+1){

		j=n/(n/i),w[++m]=n/i;

		w[m]<=sqr?id1[w[m]]=m:id2[n/w[m]]=m;

		g[m]=(w[m]-1)*k;

		h[m]=(w[m]-1);

	}

	fp(j,1,tot)for(R int i=1;1ll*p[j]*p[j]<=w[i];++i){

		int id=(w[i]/p[j]<=sqr)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];

		g[i]-=g[id]-(j-1)*k;

		h[i]-=h[id]-(j-1);

	}

	print(S(n,1)+1);

}

int main(){

//	freopen("testdata.in","r",stdin);

	init(N-5);

	int T=read();

	while(T--)solve();

	return Ot(),0;

}

巴特西

SP34096 DIVCNTK - Counting Divisors (general)(Min_25筛)

题面

题解

最新文章

热门文章