【2019GDCPC F】【hdu6537】Neko and function 题解

题目大意

  定义 $f(n,k)$ 为，把 $n$ 表示成 $k$ 个大于 $1$ 的数的积的方案数。
  （注意 $6=2 \times 3$ 和 $6=3 \times 2$ 是两种不同的方案）
  给定 $n$、$k$，求 $\sum_{i=1}^n f(i,k)$。

  $1 \leq n \leq 2^{30},~1 \leq k \leq 30$
  注意 hdu 上是有多测的但是题目没写

题解

  拆成的数必须大于 $1$，这个限制不好做，于是容斥，设 $g(n,k)$ 表示把 $n$ 表示成 $k$ 个数（允许为 $1$）的积的方案数：

$$ans=\sum_{i=0}^{k-1} (-1)^i \cdot \binom{k}{i} \cdot g(n,k-i)$$

  这个 $g$ 肯定是个积性函数了。

解法1

  用递推去考虑，考虑第 $k$ 位放什么：

$$g(n,k)=\sum_{d|n}g(d,k-1)$$

  即

$$g(k)=g(k-1)*1$$

  其中 $*$ 表示狄利克雷卷积，$1$ 表示全 $1$ 函数，即 $1(n)=1$。那么有：

$$g(k)*\mu=g(k-1)$$

  于是就可以愉快地杜教筛啦~

  然后发现杜教筛好慢，主要是预处理，预处理好写一点就 $O(nk \log n)$，要快一点可以套线性筛做到 $O(nk)$，总之就是预处理得越多，前面就越慢；预处理得越少，后面就越慢。
  我写这个做法 T 了，没去卡常，没去卡预处理，毕竟不是标算没前途~

解法2

  既然 $g$ 都是积性函数了，为什么不大力 min25 一发呢？

  $p$ 为质数时，$g(p,k)=k$，$g(p^c,k)=\binom{c+k-1}{k-1}$，这就体现出 min25 的优势了，预处理只用进行一次，筛出 $n$ 以内的质数个数就行了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxsqrtn=1e6+5, maxk=105;
const LL mo=1e9+7;

LL n;
int sqrtn,k;

int p0,p[maxsqrtn],Np[maxsqrtn];
bool bz[maxsqrtn];
void Pre(int n)
{
	fo(i,2,n)
	{
		if (!bz[i]) p[++p0]=i, Np[i]=1;
		fo(j,1,p0)
		{
			if ((LL)i*p[j]>n) break;
			bz[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
	fo(i,2,n) Np[i]+=Np[i-1];
}

LL C[maxk][maxk];
void C_Pre(int n)
{
	fo(i,0,n)
	{
		C[i][0]=1;
		fo(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
}

LL mw[maxsqrtn],g[maxsqrtn],id1[maxsqrtn],id2[maxsqrtn];
int w0;
LL min25_g(LL n)
{
	w0=0;
	for(LL i=1, j; i<=n; i=j+1)
	{
		j=n/(n/i);
		mw[++w0]=n/i;
		if (mw[w0]<=sqrtn) id1[mw[w0]]=w0; else id2[j]=w0;
		g[w0]=mw[w0]-1;
	}
	fo(j,1,Np[sqrtn])
		for(int i=1; i<=w0 && (LL)p[j]*p[j]<=mw[i]; i++)
		{
			int id=(mw[i]/p[j]<=sqrtn) ?id1[mw[i]/p[j]] :id2[n/(mw[i]/p[j])];
			(g[i]-=g[id]-(j-1))%=mo;
		}
}
LL min25_S(LL x,int j,int k)
{
	if (x<=1 || p[j]>x) return 0;
	int id=(x<=sqrtn) ?id1[x] :id2[n/x];
	LL re=(g[id]-(j-1))*k;
	for(int i=j; i<=Np[sqrtn] && (LL)p[i]*p[i]<=x; i++)
	{
		LL pe=p[i];
		for(int e=1; pe*p[i]<=x; e++, pe*=p[i])
			(re+=min25_S(x/pe,i+1,k)*C[e+k-1][k-1]+C[e+k][k-1])%=mo;
	}
	return re;
}

int main()
{
	Pre(maxsqrtn-5);
	C_Pre(100);
	
	while (scanf("%lld %d",&n,&k)!=EOF)
	{
		sqrtn=sqrt(n);
		
		min25_g(n);
		LL ans=0;
		for(int i=0, fu1=1; i<k; i++, fu1*=(-1))
			(ans+=min25_S(n,1,k-i)*fu1*C[k][i])%=mo;
		
		printf("%lld\n",(ans+mo)%mo);
	}
}