Counting Divisors HDU

设n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}n=p1c1p2c2...pmcm，则d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)d(nk)=(kc1+1)(kc2+1)...(kcm+1)。

枚举不超过\sqrt{r}√r的所有质数pp，再枚举区间[l,r][l,r]中所有pp的倍数，将其分解质因数，最后剩下的部分就是超过\sqrt{r}√r的质数，只可能是00个或11个。

时间复杂度O(\sqrt{r}+(r-l+1)\log\log(r-l+1))O(√r+(r−l+1)loglog(r−l+1))。

这道题的出题者给我膜一会，666666

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1000010,P=998244353;

int Case,i,j,k,p[N/10],tot,g[N],ans;ll n,l,r,f[N];

bool v[N];

void work(ll p)

{

	for(ll i=l/p*p;i<=r;i+=p)if(i>=l)

	{

		int o=0;

		while(f[i-l]%p==0)f[i-l]/=p,o++;

		g[i-l]=1LL*g[i-l]*(o*k+1)%P;

  	}

}

int main()

{

	//freopen("input.txt","r",stdin);

	//freopen("output.txt","w",stdout);

	for(i=2;i<N;i++)

	{

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

    	for(j=0;j<tot && i*p[j]<N;j++)

		{

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

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

    	}

  	}

	scanf("%d",&Case);

	while(Case--)

	{

		scanf("%lld%lld%d",&l,&r,&k);

		n=r-l;

		for(i=0;i<=n;i++) f[i]=i+l,g[i]=1;

		for(i=0;i<tot;i++)

		{

			if(1LL*p[i]*p[i]>r)break;

			work(p[i]);

		}

		for(ans=i=0;i<=n;i++)

		{

			if(f[i]>1)g[i]=1LL*g[i]*(k+1)%P;

				ans=(ans+g[i])%P;

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

Counting Divisors HDU - 6069

最新文章

热门文章