洛谷P3768 简单的数学题

|

好神仙的数学题呀,感觉涨了很多知识。

传送门

求$∑{i=1}^n∑{j=1}^nijgcd(i,j)$

先上反演套路:
$$
\sum_{i=1}^ni\sum_{j=1}^nj\sum_{d=1}^{n}[gcd(i,j)=d]\times d
$$
整理下式子
$$
\sum_{d=1}^{n}d\sum_{i=1}^{n/d}i\sum_{j=1}^{n/d}j[gcd(i,j)=1]
$$

反演
$$
\sum_{d=1}^{n}d\sum_{i=1}^{n/d}i\times d\sum_{j=1}^{n/d}j\times d\sum_{k|i,k|j}\mu(k)
$$
把k提到前面,枚举k的倍数
$$
\sum_{d=1}^{n}d^3\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/dk}i\times k\sum_{j=1}^{n/dk}j\times k
$$
枚举T=dk
$$
\sum_{T=1}^n\sum_{d|T}d^3\times (\frac{T}{d})^2\times\mu(\frac{T}{d})\sum_{i=1}^{n/T}i\sum_{j=1}^{n/T}j
$$
整理一下,(中间$k^2$那里有点跳步,不过应该无伤大雅)
$$
\sum_{T=1}^nT^2\sum_{d|T}d\times\mu(\frac{T}{d})\sum_{i=1}^{n/T}i\sum_{j=1}^{n/T}j
$$
这样你就有了一个60分的反演做法,不过如果你像我一样SB的话分数会在10~60不定。

这个式子显然后面整除分块,前面线筛+埃筛筛出$f(T)=T^2\sum_{d|T}d\times \mu(d)$的前缀和即可,是$n\ logn​$的。

但是其实$\sum_{d|T}d\times\mu(\frac{T}{d})$等于欧拉函数,也就是$id*\mu=\phi​$。我今天才知道

那么你就可以丢掉埃筛的log,$O(n)$做了,好的还是60分。

不过$f(x)=x^2\phi(x)$看起来就可以杜教筛。

上杜教筛公式(h(x)表示卷积的前缀和,g(x)表示杜教筛用的那个函数,s(x)表示f(x)的前缀和):
$$
g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)s(\frac{n}{i})
$$
g我们取$id^2$,那么有
$$
\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}d^2\times\phi(d)\times(\frac{i}{d})^2\

=\sum_{i=1}^ni^2\times\sum_{d|i}\phi(d)
$$
而你所不知道的是,$\phi\times 1=id​$ 我今天才知道

那么
$$
\sum_{i=1}^nh(i)=\sum_{i=1}^ni^3=(\frac{n\times(n+1)}{2})^2
$$
这个东西是个公式,我太菜了,没上过小学,但我会打表:

$1^3=1^2$

$1^3+2^3=9=3^2=(1+2)^2 $

$1^3+2^3+3^3=36=6^2=(1+2+3)^2$

$1^3+2^3+3^3+…+n^3=(1+2+3+…+n)^2$

好的那我们只有最后一个问题了,求$\sum_{i=1}^ni^2$,这个我会!!!,是$\frac{n\times\ (n+1)\times (2n+1)}{6}$。

恭喜你,通过了本题。

ps:然而并没有上面说的那么简单,你要小心这些错误:

1
for (int i=1; i<=blo; i++) phi[i]=i*i%mod*phi[i]%mod;

应该乘上1LL

1
ll num=x*(x+1)%mod*inv[2]%mod;

换成一般题看起来很正常对吧,但是x范围是1e10,就是说你必须写一个变量加一个%mod

还有,线性筛预处理的阈值开到1e7是最快的,2e6就是个弟弟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<map>
#include<cmath>
#include<cstdio>
#include<iostream>
#include <tr1/unordered_map>
#define ll long long
using namespace std;
using namespace tr1;
ll n,mod,blo,ans,inv[7],phi[10000011];
int o[10000011],prime[5000010];
inline void euler(){
o[1]=phi[1]=1;
for (int i=2; i<=blo; i++){
if (!o[i]){
o[i]=1; prime[++prime[0]]=i; phi[i]=i-1;
}
for (int j=1; j<=prime[0]&&prime[j]*i<=blo; j++){
o[i*prime[j]]=1;
if (i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j]%mod;
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]]%mod;
}
}
for (int i=1; i<=blo; i++) phi[i]=1LL*i*i%mod*phi[i]%mod;
for (int i=1; i<=blo; i++) phi[i]=(phi[i]+phi[i-1])%mod;
}
unordered_map<ll,ll> m;
ll get_phi(ll x){
if (x<=blo) return phi[x];
// puts("ok");
if (m[x]) return m[x];
ll num=x%mod*(x+1)%mod*inv[2]%mod; num=num*num%mod;
ll cl,cr;
for (ll l=2,r; l<=x; l=r+1){
r=x/(x/l);
cl=(2*l-1)%mod*l%mod*(l-1)%mod*inv[6]%mod;
cr=(2*r+1)%mod*r%mod*(r+1)%mod*inv[6]%mod;
num=(num-(cr-cl)%mod*get_phi(x/l)%mod)%mod;
}
num=(num+mod)%mod; m[x]=num;
return num;
}
int main(){
scanf("%lld%lld",&mod,&n);
blo=1e7; blo=min(blo,n); euler(); inv[1]=1;
for (int i=2; i<=6; i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
// for (int i=1; i<=n; i++){
// ans=(ans+1LL*phi[i]*sum[n/i]%mod*sum[n/i]%mod)%mod;
// }
ll a,b;
for (ll l=1,r; l<=n; l=r+1){
r=n/(n/l); ll m=n/l;
a=(get_phi(r)-get_phi(l-1))%mod,b=(m+1)%mod*m%mod*inv[2]%mod;
b=b*b%mod; ans=(ans+b*a%mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}
文章目录
,
载入天数...载入时分秒... 字数统计:75.7k