「51nood 1769」Clarke and math2

发表于

克拉克是一名人格分裂患者。某一天他变成一名数学家，在研究奇怪的东西。

他突然想算这么一个式子，给出 f(i),1≤i≤nf(i), 1 \le i \le n ，要求算：

g(i)=∑i1∣i∑i2∣i1∑i3∣i2⋯∑ik∣ik−1f(ik) mod 1000000007  (1≤i≤n,ij∈N+)\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \ \ (1 \le i \le n,i_j \in \mathbb{N}^+)

∣\mid 是整除的意思,比如 i1=5i_1 = 5 , i2=10i_2 = 10 则 i1∣i2i_1 \mid i_2。

Constraints

1≤n≤5000001 \leq n \leq 500000 ， 1≤k≤1010000001 \leq k \leq 10^{1000000}

Solution

考虑从 iki_k 到 ii 的变化过程，等价于 iki_k 乘上 kk 个数得到 ii ，实际只要求满足 kk 个数乘起来为 iik\frac{i}{i_k} 的因数的方案数即可。

对 iik\frac{i}{i_k} 分解质因数，考虑其中的一个质因子 pp 以及它的次数 xx ，利用隔板法可得当前质因子的贡献是 (k−x−1k−1)\binom{k-x-1}{k-1} （将 xx 个 pp 分配到这 kk 个数里）。

kk 很大，用 Lucas 定理可得直接将 kk 取模即可。

剩下的就直接线性筛了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n,K,cnt,now;
int f[N],inv[N],v[N],e[N],pri[N],ans[N];
bool np[N];
int read()
{
	LL x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x*10+c-'0')%mod;c=getchar();}
	return x*f;
}
int main()
{
	n=read();K=read();
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;i++)f[i]=read();
	v[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!np[i]){pri[++cnt]=i;v[i]=K;e[i]=1;}
		for(int j=1;i*pri[j]<=n;j++)
		{
			now=i*pri[j];
			np[now]=true;
			if(i%pri[j]==0)
			{
				e[now]=e[i]+1;
				v[now]=1ll*v[i]*(e[now]+K-1)%mod*inv[e[now]]%mod;
				break;
			}
			e[now]=1;
			v[now]=1ll*v[i]*K%mod;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;i*j<=n;j++)
			ans[i*j]=(ans[i*j]+1ll*v[i]*f[j]%mod)%mod;
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);
	return 0;
}