2020CCPC网络赛 Graph Theory Class （min_25素数筛 数论）

2020CCPC网络赛 Graph Theory Class （min_25素数筛 数论）

题目

http://acm.hdu.edu.cn/showproblem.php?pid=6889

题意

给你一个n个结点的完全图，结点从2~n+1标号，结点i和j之间的边权为lcm(i,j)，问你这个图的最小生成树的边权和是多少

题解

对于一个合数，我们一定能找到它的因子，那么这个点和他的因子节点相连，那么权值就是合数本身。
对于一个质数，它和所有数的lcm最小值必然是和2相连得到的最小值，所以这个权值就是2*质数。
那么这个问题就可以转化为求2~n+1的合再加上所有质数的和，数字范围1e9。这里需要用到min_25素数筛。

Min25筛

使用条件

首先要弄清楚Min25筛具体用在什么地方，有什么使用条件。一般来说，它可以求大部分的积性函数的和，即形如：
∑ i = 1 n F ( i ) \large\sum_{i=1}^nF(i) ∑i=1n​F(i)
要求的条件是F(x),x$\in$ Prime要能够用多项式表示，而且F(x^k),x$\in$ Prime要能够快速计算。

大致思想

Min25筛的大致思想，就是把这个结果分为两个部分（准确来说是三个部分），一个是i为质数的和，一个是i为合数的和，再加上i为1的函数值。那么，我们首先看如果求这个$i$为质数部分的和$ans1$。我们不妨设：

g ( n , j ) = ∑ i = 1 n F ( i ) [ i ∈ P o r m i n ( p ) > P j , p ∣ i , p ∈ P ] \large g(n,j)=\sum_{i=1}^nF(i)[i\in P\ or \ min(p)>P_j,p|i,p\in P\ ] g(n,j)=∑i=1n​F(i)[i∈P or min(p)>Pj​,p∣i,p∈P ]

$g(n,j)$表示$n$以内所有质数以及最小质因子 > P j >P_j >Pj​的合数的$F$之和。这样，显然有$ans1$等于$g(n,|P|)$。

这个东西的实际含义是什么呢？可以参考一下埃氏筛法的运行过程。

假设现在有n个数依次排开，第i个数是$f(i)$，根据埃氏筛法的那套理论，每次选出一个质数，然后筛掉它的所有倍数。

会发现$g(n,j)$就是运行$j$次埃氏筛法后，没被筛掉的所有数之和加上所有的$f(p)$。

我们要求的 a n s 1 = ∑ i = 1 x [ i 是 质 数 ] f ( i ) ans1 = \sum_{i=1}^x[i是质数]f(i) ans1=∑i=1x​[i是质数]f(i)其实就是$g(x,|P|)$，其中|P|是质数集合的大小。

那么我们考虑如何去计算这个$g(n,j)$。

我们发现，当 P j 2 > n P_j^2>n Pj2​>n时，最小质因子是 P j P_j Pj​的最小合数就是 P j 2 P_j^2 Pj2​，而 P j 2 > n P_j^2>n Pj2​>n，所以此时有：

$g(n,j)=g(n,j-1)$。

当 P j 2 < n P_j^2Pj2​<n时，我们考虑从$g(n,j-1)$转移到$g(n,j)$时少了什么东西，显然少了的就是最小质因子恰好是 P j P_j Pj​的和，所以要把这一部分给减去。还是考虑用$g(x,y)$来表示这一部分的结果，于是有：

g ( n , j ) = g ( n , j − 1 ) − F ( P j ) [ g ( n P j , j − 1 ) − g ( P j − 1 , j − 1 ) ] \large g(n,j)=g(n,j-1)-F(P_j)[g(\frac{n}{P_{j}},j-1)-g(P_j-1,j-1)] g(n,j)=g(n,j−1)−F(Pj​)[g(Pj​n​,j−1)−g(Pj​−1,j−1)]

总的来说减去的部分本身也是两个部分，首先是要把 P j P_j Pj​这个最小质因子提出来，那么剩下的和就是 g ( n P j , j − 1 ) g(\frac{n}{P_{j}},j-1) g(Pj​n​,j−1)，但是这个里面还是包含了那些最小质因子小于 P j P_j Pj​的部分，而我们要求的是最小质因子恰好是 P j P_j Pj​的和，所以还要减去最小质因子小于 P j P_j Pj​的部分，这就是 g ( P j − 1 , j − 1 ) = ∑ j − 1 i = 1 f ( P i ) g(P_{j}-1,j-1)=∑j−1i=1f(Pi) g(Pj​−1,j−1)=∑j−1i=1f(Pi)。

这样一来g(n,j)总的递推公式就是：

g ( n , j ) = { g ( n , j ) = g ( n , j − 1 ) P j 2 > n g ( n , j − 1 ) − F ( P j ) [ g ( n / P j , j − 1 ) − g ( P j − 1 , j − 1 ) ] P j 2 ≤ n \large g(n,j)= \begin{cases} g(n,j)=g(n,j-1) & P_j^2 > n \\ g(n,j-1)-F(P_j)[g(n/P_j,j-1)-g(P_j-1,j-1)] & P_j^2\le n \end{cases} g(n,j)=⎩⎨⎧​g(n,j)=g(n,j−1)g(n,j−1)−F(Pj​)[g(n/Pj​,j−1)−g(Pj​−1,j−1)]​Pj2​>nPj2​≤n​

举个例子

我这个人学习东西就喜欢用一些实际的东西去展示算法或者公式，可能是想象能力不太足把。
我们设积性函数$F(x)=x$
我们要计算 ∑ i = 1 20 F ( x ) [ x ∈ P ] \sum_{i=1}^{20}F(x)[x\in P] ∑i=120​F(x)[x∈P]就是求20以内的所有素数和。
那么考虑一下 g ( 20 , 0 ) = ∑ i = 1 20 i = 210 g(20,0) = \sum_{i=1}^{20}i = 210 g(20,0)=∑i=120​i=210
那么$g(20,1)$表示的就是经过第一次埃式筛法后筛选出来的数字。
第一次筛选出来的数字都是2的倍数，比如：4，6，8，12，14，16，18，20.
所以筛选出来的数字用数学公式表达就是：
$F(2)g(20/2,0)-F(2)g(1,0)$
= 2 ∗ ( ∑ i = 1 10 − 1 ) = 98 =2*(\sum_{i=1}^{10}-1)=98 =2∗(∑i=110​−1)=98
所以$g(20,1)$
$=g(20,0)-[F(2)g(20/2,0)-F(2)g(1,0)]$
$=210-98=112$
同理
$g(20,2)=g(20,1)-[F(3)g(20/3,1)-F(3)g(2,1)]$

继续拓展

我们刚才计算的是计算所有素数和。要解决更加深入的问题还要继续讨论。

作为积性函数，$F(i)$的表达式肯定是分段的，如果i是质数，那么会有一个通项公式，如果是合数，那么可以是各个质因子的乘积。

现在我们已经处理完了i为质数时的和，那么现在考虑直接求总和，考虑质数的和直接用，1的值单独算，所以主要是合数部分。与之前类似，我们令：
S ( n , j ) = ∑ i = 1 n F ( i ) [ m i n ( p ) ≥ P j , p ∈ P , p ∣ i ] \large S(n,j)=\sum_{i=1}^nF(i)[min(p)\ge P_j,p\in P,p|i\ ] S(n,j)=∑i=1n​F(i)[min(p)≥Pj​,p∈P,p∣i ]

$S(n,j)$表示从$1$累加到$n$的$F(i)$，同样的，$i$要么是质数，要么最小质因子大于 P j P_j Pj​。与上面不同，我们这里要求的是倒过来的，最后需要的答案就是$S(n,1)$。类似的，我们可以得到下面的递推式：

S ( n , j ) = g ( n , ∣ P ∣ ) − ∑ i = 1 j F ( P i ) + ∑ k ≥ j ∑ P k e + 1 < n ( F ( P k e ) S ( n P k e , k + 1 ) + F ( P k e + 1 ) ) \large S(n,j)=g(n,|P|)-\sum_{i=1}^{j}F(P_i)+\sum_{k\ge j}\sum_{P_k^{e+1}< n}(F(P_k^e)S(\frac{n}{P_k^e},k+1)+F(P_k^{e+1})) S(n,j)=g(n,∣P∣)−∑i=1j​F(Pi​)+∑k≥j​∑Pke+1​<n​(F(Pke​)S(Pke​n​,k+1)+F(Pke+1​))

关于这个前一部分 g ( n , ∣ P ∣ ) − ∑ i = 1 j F ( P i ) g(n,|P|)-\sum_{i=1}^{j}F(P_i) g(n,∣P∣)−∑i=1j​F(Pi​)，这个就是相应的质数部分的和，用所有质数的和，减去前j个质数。主要是后面这个合数部分。因为F(i)是积性函数，所以对于一个合数，我们可以把它的最小质因子包括其幂次的那一项提出来，提出来之后，剩下的部分就不包含这个最小质因子了，对应的和就是 S ( n P k e , k + 1 ) S(\frac{n}{P_k^e},k+1) S(Pke​n​,k+1)。然后这里e的范围是要求 P k e + 1 < n P_k^{e+1}Pke+1​<n因为要保证 n P k e > P k \frac{n}{P_k^e}> P_k Pke​n​>Pk​，这样最小质因子大于第k个数字。但是，注意到，这样子可以筛出大部分合数，但是对于形如 P k i , i > 1 P_k^i,i>1 Pki​,i>1这种合数，我们并没有计算到，所以我们单独把这个加上。

还是一样，进行数论分块求和递推，就可以求出最后的S(n,1)。再把F(1)加上即可。

总的来说就是这样，分成质数、合数和1三个部分来做，时间复杂度很玄学的 O ( n 3 4 log ⁡ n ) O(\frac{n^{\frac{3}{4}}}{\log{\sqrt{n}}}) O(logn ​n43​​)，

AC代码

#include
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
ll f1[maxn],f2[maxn];
ll mod;
ll powmod(ll a,ll b)
{ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll C(ll x)
{return (x+1)*x/2;
}
ll query(ll k)
{if(!k)return 0;ll lim=sqrt(k);for(ll i=1; i<=lim; i++)f1[i]=C(i),f2[i]=C(k/i);for(ll p=2; p<=lim; p++){if(abs(f1[p]-f1[p-1])==0)continue;ll xx=p;for(ll i=1; i<=lim/p; i++)f2[i]-=(f2[i*p]-f1[p-1])*xx;for(ll i=lim/p+1; p*p*i<=k&&i<=lim; i++)f2[i]-=(f1[k/i/p]-f1[p-1])*xx;for(ll i=lim; i>=p*p; i--)f1[i]-=(f1[i/p]-f1[p-1])*xx;}return f2[1];
}
int main()
{int T=1;scanf("%d",&T);while(T--){ll n,k;scanf("%lld %lld",&n,&k);mod = k;ll temp = powmod(2,mod-2);ll sum = (3 + n + 1) % k * ((n - 1) % k) % k * temp % k;ll s1 = ll(query(n+1)) % k;ll s2 = ll(query(2)) % k;ll s3 = (s1%k - s2%k + k) % k;printf("%lld\n",ll(s3+sum)%mod);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！