2019国家集训队论文《整点计数》命题报告 学习笔记/Min25

$2019$国家集训队论文《整点计数》命题报告 学习笔记/$Min25$

补了个大坑

看了看提交记录,发现$hz$的$xdm$早过了...

前置知识,$HAOI$《圆上的整点》

题目要求计算所有$(x,y),$满足$x^2+y^2=r^2$的点数

这个题尽管原来做过,但是当时式子都是别人带着推的,并不知道深层原因,今天才发现这个和复数有关

先自己推一下式子

$x^2+y^2=r^2$

$y^2=r^2-x^2$

$y^2=(r-x)(r+x)$

$y=\sqrt{(r-x)(r+x)}$

$d=gcd(r+x,r-x)$

$A=\frac{r-x}{d},B=\frac{r+x}{d}$

$gcd(A,B)=1$

$y^2=d^2\times A\times B$

这里的话$A,B$必然是完全平方数

$A=a\times a,B=b\times b$

$a^2+b^2=\frac{2\times r}{d}$

有了这个式子,代码就好写了,枚举$gcd$枚举$a,b$就好了

这个的启发意义是什么,或许是提取$gcd$

复杂度$O(r^{\frac{3}{4}})$

$LOJ$整点计数

这道题和上道题区别在于一个是求圆上,一个是求圆内

好,暴力的想一想,首先可以枚举所有的整数长度的半径,用一下$HAOI$圆上的整点的思路

复杂度$O(r^2)$

那么到这里思路枯竭了,数学题,打表是必须的

那么对于函数$f(x)$打个表m发现都是$4$的倍数,其实到这里可以很自然的想到,同时除以一个$4$,发现这是一个积性函数(才怪...)

那么到了这发现是$4$的倍数,那么$\mod 2^k$是$0$(可以直接输出$0$得到两个测试点分数的好成绩)

考场上想到了在勾股数上搞事情

也想到了找到最小的互质的勾股数然后扩大倍数计算的方法

这个东西的复杂度不太知道,但是由于你可以打表得出范围内的勾股数,那么整一下就好了

得到所有勾股数,然后看看在这个范围内有多少个就好了

以上都是本题暴力部分

下面的部分就和高斯整数有点关系了

二维平面考虑复数$x+yi$

我们要求的是$\sqrt{x^2+y^2}<=r$并且是整数

怎么保证这个是整数,话说考试时候被这个东西卡住了

$x^2+y^2=(x+yi)(x-yi)$

那么我们对于每个$f(x)$而言,他的数值等于所有的高斯整数与其共轭高斯整数的和是$x^2$的对数

我们如何不重不漏的计算每一个满足要求的整点

考虑一下一个整数什么是唯一的,一个数的质因数分解是唯一的,那么我们想不重不漏计算每一个整数,那么可以枚举质因数分解来唯一确定

那么同理可得,对于任意一个高斯整数,必然有一个唯一分解,只不过这个分解是高斯素数分解

那么我们可以枚举每个高斯素数出现的次数,不重不漏的计算每个点

高斯质数$--$不能被继续分解的高斯整数...

质数相乘得到整数,那么质数怎么被唯一分解

费马平方和定理

首先明确,我们要分解整数,那么肯定是分解成共轭相乘的形式,否则无法消掉复数

那么需要能找到一个$a,b,a^2+b^2=p^2$

那么这个$p$有解的条件是$p\mod4=1$

那么$4k+3$的质数由于不能继续分解,那么也是高斯质数,但是$i$的系数是$0$

还是说怎么快速求$f(x)$

首先要对$x$质因数分解,发现这都是$4$的倍数,那么继续考虑这个情况

$\frac{f(225)}{4}=\frac{f(9)}{4}\times \frac{f(25)}{4}$

这个式子就是说,$f(9)$和$f(25)$分解方式相乘肯定是总的,必然不会重复

其实到这就很好说了,你无非是把这个分解之后,看看有多少种组合方式罢了

那么考虑对$4k+3$进行分解,必然是$x^{\frac{k}{2}}\times x^{\frac{k}{2}}$

我需要重新想一想

首先我们要求的是$f(x)$

也就是所有的$a^2+b^2=x^2$的$(a,b)$

就是求所有的$x^2$的$(a+bi)\times(a-bi)$的形式

那么我们肯定分解的是$x^2$是完全平方数

首先我们分解出来的必须是共轭形式,那么这个显然只能分解出来开根号的形式

那么$4k+1$型质数

首先$p$有唯一分解$(a+bi)\times(a-bi)$

那么对于他的$k$次幂我们有$(a+bi)^x(a-bi)^x$的分解形式

那么我们能分解的形式肯定是俩互为共轭

那好说了,$(a+bi)^k(a-bi)^{x-k}\times (a+bi)^{x-k}(a+bi)^k$

这个这个必为共轭

那么方案数也显然了$k+1$种情况

至于为什么不讨论$4k+2,4k$

原因很简单,因为这个无法被分解出共轭的形式,必然不会有一个复数满足

那么式子很好得出

我们先$x^2$

那我们对$x^2$进行质因数分解就好了,我们要求出所有满足条件的共轭复数,

$f(x)=4\times\Pi_{i=1}^{s}(1+[p_i=1(\mod 4)]\times k_i)$

这个东西把每个质数提前预处理一下,然后搞一波埃筛

枚举$x$,质因数分解累计答案,每个质数由于是唯一分解且只有两项,那么每一个质数的贡献答案次数就显然了

要优化这个暴力的话,可以考虑分块打表,尽管很麻烦...

到了这,离正解就很近了

上面推导了一个性质,每一个质数必须独立分解成一对共轭复数的乘积

上面那个式子也能看出来,$f(x)/4$是一个积性函数

那么对于原来的式子重新变形

$\sum_{i=1}^{n}f(i)^k=4^k\times \sum_{i=1}^{n}g(i)^k$

好,积性函数,好,前缀和,好$Min25$

来,咱们重新回顾一下$Min25$,好久没写都忘了...现在就会$PN$筛了...

话说回来,确实$PN$筛好写又好构造,但是有些题确实只能$Min25...$

$Min25$筛

**用途**

亚线性复杂度求出积性函数前缀和

对于一个积性函数$F(x)$,用来快速计算前缀和$\sum_{i=1}^{n}F(i)$

这个积性函数需要满足$F(x)[x\in Prime]$可以用多项式表示

同时需要$F(x^k)[x\in Prime]$能够快速计算

先不考虑前缀和的东西,考虑一个积性函数$F(x)$

求$\sum_{i=1}^{n}[i\in Prime]F(i)$

假设函数是$F(x)=x^k$

那么求解$\sum_{i=1}^{n}[i\in Prime]i^k$

设$P$是质数集合,$P_i$是第$i$个质数

这个的本质是$dp$转移,很$nb...$

设$g(n,j)=\sum_{i=1}^ni^k[i\in P\ or \ min(p)>P_j,p|i,p\in P\ ]$

表示计算$1-n$里面所有的质数或最小质因子大于$P_j$的元素的$k$次方和

分情况讨论,明确一下,肯定是从小向大转移

$P_j^2>n,$那么首先对于第二个合数部分肯定没有贡献,那么可以直接转移$g(n,j)=g(n,j-1)$

这部分意思是说,首先对于质数部分,前面的肯定不会发生变化,后面的合数部分,由于不会出现,那么直接转移就好了

那么$P_j^2<=n$就需要减去一部分了

我们们减去的肯定是最小质因子是$P_j$的合数了,大概减的是$F(P_j\times...)$的形式

由于是积性函数,我们可以提出一部分$F(P_j)\times F(...)=P_j^k\times F(...)$

首先把所有的提出一个$P_j$出来,然后考虑我们要减去上限是$\frac{n}{P_j}$内的所有质因数大于等于$P_j$的合数

由于减去一些最小质因数小于的数字,那么应该加上一些质数

式子易得

$g(n,j)=g(n,j-1)-P_{j}^k[g(\frac{n}{P_{j}},j-1)-g(P_j-1,j-1)]$

$g(n,|P|)$就是所有质数的$i^k$

我们计算的时候要分成两部分,一个是质数部分,一个是合数部分,那么质数部分是$f(n,|P|)$

那么两个转移式子合并到一起

$g(n,j)= \begin{cases} g(n,j-1)&P_j^2\gt n\\ g(n,j-1)-P_{j}^k[g(\frac{n}{P_j},j-1)-g(P_j-1,j-1)]&P_j^2\le n \end{cases}$

这个$g$只是一个辅助转移的工具,当然这个值和我们要求的前缀和有一些出入,当然了,我们每个数都按照那个式子求的结果,并不是每个数都能带入式子

考虑一下$g$的过程,首先有$g(x,0)$所有数字的和,然后一步步减去某些最小质因子等于一个数字的数

这个式子只有在集合里面全是质数的时候才是正确的

顿时感觉$Min25$比$PN$也不复杂...

我们有了所有质数位置的$F(i),$我们要求所有的和

继续设$S(n,j)=\sum_{i=1}^{n}[min(p)>=P_j]f(i)$

和上面的定义很类似,也是$1-n$里面最小质因数大于等于$P_j$的$F(i)$的和,这个和质数无关

最后答案是$S(n,1)+F(1),$$1-n$所有的最小质因数大于等于$2$的$F(i)$的和再加上$F(1)$就好了

最后的式子也是分成质数和合数分开计算

$S(n,j)$表示$1-n$所有最小质因子大于$P_j$的数字的函数值得和

$S(n,j)=g(n,j)-\sum_{i=1}^{j-1}f(P_i)+\sum_{k=j}^{P_k^2\le n}\sum_{e=1}^{P_k^{e+1}\le n}(S(\frac{n}{P_k^e},k+1)\times f(P_k^e)+f(P_k^{e+1}))$

首先由于质数合数分开计算,那么前面就是质数部分,而且要保证最小质数的质因子大于$P_j,$那么需要减去小于$P_j$的所有质数,然后加上合数部分,这个很好说,枚举最小质因数和出现次数就好了,我们把最小质因子等于一个数字的一起计算

由于这个东西是积性函数,那么显然的,可以提出来分开算,当然需要保证互质,剩下部分就是了,我这式子前半部分并没有求一个质数的几次方形式,所以后面要加上这一部分

一会还要去补$DDP$....