【叉姐NOIP模拟赛】Lcmsum

实际上我并没有看过叉姐的这几套题。。搜也搜不到。。

不过solution写是叉姐的题那就是吧

Description

小P最爱数论了,他每天都做很多数论题,有一天,他请教了我一个问题

简单来说,就是求

$$\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(A_i,A_j)$$

其中,A是给定的长度为n的正整数序列

而我的数论实在太渣,所以来问你了

Input

第一行,一个正整数n

第二行n个正整数,表示A序列

Output

一行一个正整数表示答案

Data Range

30%:\(n<=1000\)

另40%:\(A_i=i\)

100%:\(n\le 100000,max(A_i)\le 100000\)

Solution

当高二神犇们在考这道题的时候,我请了两节课假到机房来

看到第一题好像很可做的样子?感觉和能量采集差不多的样子?

赶快动手推

推了半天无果 到UOJ群里求助

C1

%%%一眼秒题

然后看着今年论文学了一下。。感觉并没有什么卵用 并不能找到f(x)和g(x)这样的东西。。

然后求助r_64

r_64推了一下然后:r1 然而标解一个\(log\)

所以还是去求助了Claris

期间看Claris没有回复以为他不理我了。。于是去问了YMD

YMD给了一种不用莫比乌斯反演的做法。。打表找到了一个积性函数。。%%%

然后Claris回我了。。带上一张图片

Claris的真传

太强了。。而且写的好认真。。果然是为人民造福的好神犇

另外好像r_64就是推到那个黑点之前了,再往后推推就能得到\(nlogn\)的做法%%%

Claris都写得这么好了我也没什么好说的了

不过还是总结一下:这道题似乎并不是用的莫比乌斯反演而是莫比乌斯函数的第一个性质

也就是

$$\sum_{d|n}\mu(d)=\begin{cases}
1&n=1\\
0&n\ne 1\\
\end{cases}$$

可以利用它将一些[k=1]的条件转化为数学问题方便推导

但是!还没完

看到%zzd的代码发现其实这题不需要这么麻烦的

令\(f(i)=\sum_{gcd(a,b)=i}a\times b\)

那么\(ans=\sum{f(i)/i}\)

其中\(f(i)\)可以像能量采集一样倒推容斥求

由于数据水不需要开高精度所以代码非常短

说点什么

  Subscribe  
提醒