大佬们绕道吧（或跳到错误&启发后下一根横线后）

这道题吧正解是莫比乌斯反演吧，但本人有一种独创玄妙的想法去偏分

这道题是让我们求这个对吧

$(\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j))~mod~p$

先把$\sum_{i=1}^n\sum_{j=1}^n$内的$ij$去掉式子变成了$(\sum_{i=1}^n\sum_{j=1}^n gcd(i,j))~mod~p$

怎么算呢
$(\sum_{i=1}^n\sum_{j=1}^n gcd(i,j))~mod~p$
如果$n$小我们本来就可以模拟来算，但这道题的简化版$n$都$10^6$级别的肯定没办法,

考虑我们老师提出的一种思路，既然一个一个i（一对一对$ij$）来算没办法，那么如果我们规定答案又如何

这样我们就可以去找个数累乘即可

但怎么在这样浩如烟海的数据找出一对$gcd(i,j)=x$呢

既然这样，再简化问题，我们能否将双向的求$gcd$改为单向的呢，即只计算比i大的每个j$(\sum_{i=1}^n\sum_{j=1}^n gcd(i,j))~mod~p$

这样问题变为了$(\sum_{i=1}^{n-1}\sum_{j=i}^n gcd(i,j))~mod~p$

又即$(\sum_{i=2}^{n}\sum_{j=1}^i gcd(i,j))~mod~p$

而怎么变回刚才的式子呢，很简单

考虑这样全体点即数字的双向运算，共分为三类，即左向右，右向左和自己对自己

所以上式=$2\cdot\sum_{i=2}^{n}\sum_{j=1}^i gcd(i,j))~mod~p+n\cdot(n+1)/2$

到此，我们可以正式来思考这个问题了

如果i与某一个小于数的$gcd$不为1，则这个数一定是i的因数

考虑x与i的$gcd$为它的第k个因数$p_k$，则只要$gcd(x/{p_k},i)=1$即可，这时x的个数就是与i互质的数个数，即$φ(i)$

但我们必须要求出这每个$i$与它如上文所求出的$F_i$吗

不，对于每一个i我们的确需要求出其每一个因数对$F_i$造成的影响

但对于上式$Ans$=$\sum_{k=1}^{i}{F_i}$中一个数x就不只对结果造成一次影响了，而是$x\cdot1,x\cdot2,x\cdot3,...x\cdot(i/x)$了

因此模仿着筛法我们写下这样的代码

$\sum_{i=1}^{n/2}\sum_{j=2}^{n/i} i\cdotφ(j))~mod~p$

好吧

你现在已经可以做出$ P2398 GCDSUM$和$P1390$了

但别急，我们还是没有做出最初的话题

先来一波相似的变形

$\sum ^{n}_{i=1}\sum ^{n}_{j=1}ij\gcd \left( i,j\right)$

$=2\sum ^{n/2}_{i=1}\sum ^{n/i}_{j=2}ij\gcd \left( i,j\right)+\sum _{i=1}^{n}i^3$

于是后面那一坨又变成了${(\sum _{i=1}^{n}i^2)}^2$

即$n^2\cdot(n+1)^2$

考虑

$\sum ^{n/2}_{i=1}\sum ^{n/i}_{j=2}ij\gcd(i,j)$……（1）

与$\sum ^{n/2}_{i=1}\sum ^{n/i}_{j=2}\gcd(i,j)$……（2）

每个$gcd$我们求出来了，那么乘上了$i\cdot j$应该也好算吧

既然在原式$\sum_{i=1}^{n/2}\sum_{j=2}^{n/i} i\cdotφ(j))~mod~p$中

i表示的是$gcd$的值，直接乘上去即可

j表示的是$gcd$的个数，我们也可以换个角度理解为是每次有$gcd(n,x)=p_i$时权值为1

因此要求的是因此要求的是与j互质的数的个数

而现在的（2）式中不过权值被改成了$x$罢了

我们只需要求出对于（1）式中的每一个j互质的数的和

仔细想想（1）（2）是相通的吧

而这个数怎么求呢

考虑如果x($<n$)与n互质，则n-x也与n互质

因此与n互质的数总是成对出现且对数为$φ(n)/2$

（是这样的吗）

严谨来说这并不对

还需要考虑n为偶数情况

但这样答案是一样的啊

所以我们肯定的说与n互质的数之和为$n\cdot φ(n)/2$

我们得到了一个仿佛正确的式子

$\sum_{i=1}^{n/2}\sum_{j=2}^{n/i} i^2\cdot j^2\cdot φ^2(j)/2~mod~p$

正好与前面单双向抵消掉了一个$1/2$多么美妙啊

${}$

你觉得自己看完这些个就该走了吗亦或一个$copy$漂亮$AC?$

好吧如果你还坚持看到了这里那么你肯定知道那是错的

有没有很伤心

** 其实我比你还伤心 **

但在继续之前有必要说明一下原因呢

其实感觉起来每一步都没错，但其实这样一个代还的过程就错了

在原式中的$ij$仅仅是两个没有关系的变量，他们中的每一个都有可能成为后文中所写的x

而在我们的变形中i表示的是结果，和他对应的上文中的$(i0,j0)$太多了，而j则是表示的这样存在的x的个数，我们把（1）（2）式的区别归结到权值是没错，但$i,j$的值是被分别累乘到很多对对的包含它们的数对$gcd$上，而我们这么做，是把i，j乘到了满足gcd为x，其中它们成立的这样很多组之中，就大错特错了

刚才的那一段

考虑用另外一种方式表示所求

【注明】以下内容均省略mod p

先不分离方向，思考能否把$i\cdot j$外部分不脱离的表示出来(就是整体的式子不变)，即表示$gcd(i,j)$

有定理如下：

一个数的所有因子的欧拉函数之和等于这个数本身。

因为最大公约数是所有公约数的倍数，所以他就是他们的欧拉函数之和

有$gcd(i,j)=\sum _{(x|i,x|j)} φ(x)$

仿佛我们需要判定求和一样

但在刚才一题给我们的启发————构造思路中我们可不可以反着去枚举这样的x去当别人的公约数,再去求所有它不同倍数成对之积的和？

即$\sum_{x|i,x|j}i\cdot j$

答案是肯定的，并且刚才提到的两种思路应该是对等的

怎么快速的求这些乘积的和,同样思考构造，既然x只要是$i,j$的公约数就可以了，那么可以直接认为$i=k_1\cdot x,j=k_2\cdot x$，而其中k1,k2取值都是$[1,[n/x]]$（这里[]下除法表向下取整），又因为$i,j$在这里地位是平等的
k1会取到的值k2都有可能取到

所以$\sum_{x|i,x|j}i\cdot j$=$(x\cdot \sum_{i=1}^{n/x})^2$

所以就有原式$=\sum ^{n}_{i=1}φ(i)\cdot (i\cdot \sum_{j=1}^{n/i})^2$

$=\sum ^{n}_{i=1}φ(i)\cdot (i\cdot n\cdot (n+1) )^2$

关键就是这道题$mod$的数极大无比，我们可以用上快速乘，同时用上快速幂，也可以这样变形

$\sum ^{n}_{i=1}φ(i)\cdot i^2\cdot \sum_{j=1}^{n/i}j^3$

最后提示下筛法时直接保存$φ(i)\cdot i^2 modp$的值

最后声明

前一个错误的思路is by myself

这个思路is by我老师的提示

个人认为$ P2398 GCDSUM$和$P1390$大家可以用两种方法试一试

巴特西

luoguP3768简单的数学题

有没有很伤心

有没有很伤心

有没有很伤心

** 其实我比你还伤心 **

【注明】以下内容均省略mod p

最后声明

最新文章

热门文章