【2021 ICPC Gran Premio de Mexico 2da Fecha F】Flipped Factorization 题解

题目大意

  设 $x$ 的质因数分解为 $p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，记 $f(x) = c_1^{p_1}c_2^{p_2}\cdots c_m^{p_m}$，给定 $n$，求 $\sum_{i=1}^n f(n) \bmod 10^9+7$。

  $n \le 10^{14}$
  10s

题解

  $n$ 的这个范围没法筛，但却很根号。
  因此用 powerful number 求积性函数和。

  观察到对质数来说 $f(p)=1$，能对上这个形式的，马上想到全 1 函数 $1(n)=1$。然后观察 $h = \frac{f}{1} = f \ast \mu$，得到

$$h(p^c)=\begin{cases} c^p-(c-1)^p, &c>1 \\ 0, &c=1 \end{cases}$$

  然后推式子

$$\begin{aligned} & f = h \ast 1 \\ \Rightarrow & \sum_{i=1}^n f(i) = \sum_{i=1}^n \sum_{j=1}^{\lfloor \frac ni \rfloor} h(i)1(j) = \sum_{i=1}^n h(i) \lfloor \frac ni \rfloor \\ \end{aligned}$$

  又由于 $h$ 只在 powerful number 处有值，因此用 dfs 把 $O(\sqrt n)$ 个 powerful number 都找出来算答案就行了。dfs 的过程中要维护 $h$ 的值，$c^p$ 可以用快速幂算。

代码

#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 maxp0=1e7+5;
const LL mo=1e9+7;

LL n;

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

LL Pow(LL x,LL y) {
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

LL ans;
void dfs(int k,LL h,LL i) {
	if (k>p0) return;
	if (n/i<(LL)p[k]*p[k]) return;
	dfs(k+1,h,i);
	LL last=1;
	i*=p[k];
	for(int c=2; ; c++) {
		LL cur=Pow(c,p[k]);
		LL newh=h*(cur-last+mo)%mo;
		i*=p[k];
		(ans+=(n/i)%mo*newh)%=mo;
		dfs(k+1,newh,i);
		if (n/i<p[k]) break;
		last=cur;
	}
}

int main() {
	Prime(1e7);
	
	scanf("%lld",&n);
	
	ans=n%mo;
	dfs(1,1,1);
	
	printf("%lld\n",ans);
}