【2020百度之星初赛一 1008】【hdu6750】Function 题解

题目大意

  记 $f(n)$ 表示 $\sum_{d|n,\ \gcd(n,\frac nd)=1}d$，给定 $n$，求 $\sum_{i=1}^n f(i) \bmod 10^9+7$。

  $n \le 10^{12}$
  多测，10 组数据，20s，32768K 。

首先

  明眼人一看就有

$$f(n) = \prod_{i=1}^m(1+p_i^{c_i})，其中\ n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$$

  这显然是个积性函数。

解法1

  一看，积性函数求和；
  再一看，$f(p)=1+p$，意味着 min25 第一步就是求个质数和+质数个数；
  再再一看，给了 20s。

  行，min25，不跟你多 BB

  。。。
  。。。
  。。。
  （半天后）
  。。。

  WOC，0202 年了居然还有内存 32MB 的题！！？？？

解法2

  于是乎 min25 出于它不可压缩的至少 40MB 的内存，惨遭毒手。。。

  所幸积性函数求和不止一种方法。这里用的是 powerful number，用这个到后面化简起来巨优秀。

  先访问这里学一下 powerful number
  （第一次学就写详细点。。。）
  观察到 $f(p)=1+p$，能跟这个形式凑上的，马上想到 $\sigma(n)=\sum_{d|n}d$ 。
  于是构造 $h(n)=\frac{f(n)}{\sigma(n)}$（狄利克雷卷积的除法），这个 $h(n)$ 就会满足只在 powerful number 处有非 $0$ 值。推一下发现这个 $h(n)$ 长得很好看：

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

  进一步有

$$h(n)=\begin{cases} \mu(\sqrt n) \cdot \sqrt n & , n\ 是完全平方数 \\ 0 &, \text{else} \end{cases}$$

  设 $S_{\sigma}(n) = \sum_{i=1}^n \sigma(i)$，于是有：

$$\begin{aligned} \sum_{i=1}^n f(i) &= \sum_{i=1}^n \sum_{j=1}^{\lfloor \frac ni \rfloor} h(i)\sigma(j) \\ &= \sum_{i=1}^n h(i) \cdot S_{\sigma}(\lfloor \frac ni \rfloor) \\ &= \sum_{i=1}^{\lfloor \sqrt n \rfloor} \mu(i) \cdot i \cdot S_{\sigma}(\lfloor \frac{n}{i^2} \rfloor) \end{aligned}$$

  前面 $\mu$ 线筛出来，后面 $S_{\sigma}(\lfloor \frac{n}{i^2} \rfloor)$ 每次分块求：

$$S_{\sigma}(m) = \sum_{i=1}^m i \lfloor \frac mi \rfloor$$

  总的时间复杂度为

$$\sum_{i=1}^{\sqrt n} \sqrt{\lfloor \frac{n}{i^2} \rfloor} = \sqrt n \sum_{i=1}^{\sqrt n} \frac 1i = O(\sqrt n \ln 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, maxp0=80000, maxw0=2e6+5;
const LL mo=1e9+7, inv2=5e8+4;

LL n;
int sqrtn;

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

inline LL sum(LL x,LL y) {return (x+y)%mo*((y-x+1)%mo)%mo*inv2%mo;}
LL S(LL n)
{
	LL re=0;
	for(LL i=1, j; i<=n; i=j+1)
	{
		LL x=n/i;
		j=n/x;
		(re+=sum(i,j)*x)%=mo;
	}
	return re;
}

int T;
int main()
{
	Prime(1e6);
	
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld",&n);
		sqrtn=sqrt(n);
		
		LL ans=0;
		fo(i,1,sqrtn) if (mu[i]!=0) (ans+=mu[i]*i*S(n/((LL)i*i)))%=mo;
		
		printf("%lld\n",(ans+mo)%mo);
	}
}