$\text{LuckyLeaves}$ 手把手教你入门莫反。
题目传送门以及原题地址。
推式子：
首先有：
$\displaystyle\sum_{i=1}^{n}\sum_{j=i+1}^{n}\operatorname{lcm}(a_i,a_j)=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{lcm}(a_i,a_j)-\sum_{i}^{n}a_i$
这是显然的，而现在我们就将 $i,j$ 提到了同等地位。
因为有 $a_i\leq10^6$ ，那么，我们可以从值域方面来考虑，这里记 $cnt[i]$ 为 $a_j=i$ 的个数。
继续推式子：
然后使用提前思想，得到：
然后，就会发现（其实应该早就可以发现），$cnt[i]$ 已经具有了 $[dp|i]$ 的功能了。
所以再次化简式子（令 $N=1e6$）：
然后设出 $T=pd$ ：
再设：
则有：
有 $Mub[],Num[]$ 的预处理，时间复杂度为 $\mathcal O(n\ln n)$ ，然后枚举 $T$ 的时间复杂度为 $\mathcal O(n)$ ，则这道题的时间复杂度为 $\mathcal O(1e6\ln 1e6+1e6)=\mathcal O(7e6)$ 。
然后说一个调了很久的 $\text{Bug}$ ，因为答案是：
$\displaystyle ans=\frac{1}{2}\sum_{T}^{N}T\times Mub[T]\times Num[T]^2-\sum_{i}^{n}a_i$
因为是模意义下的运算，所以这里不能直接做除法，而是需要乘上逆元。
不过 $2$ 的逆元一向好求：$inv[2]=(Mod+1)/2$ 。
上述是以 $p$ 转换的，还可以保留 $d$ 消 $p$ 的做法，不过那样子做会有一个线性求逆元的过程，且众所周知，逆元容易出锅。
对于数学题而言，总是一个化繁而简的过程。
AC Code
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
const int MAXN=2e5+10;
const int MAXS=2e6+10;
const int Mod=998244353, inv=(Mod+1)/2;
int N,Tot,MaxNum,Sum;
int Cnt[MAXS],Num[MAXS],Mub[MAXS];
int Mu[MAXS],G[MAXS],Pri[MAXS];
bool Is[MAXS];
inline void sieve(int n)
{
for(int T=1;T<=n;++T)
for(int i=1;T*i<=n;++i)
Num[T]=(Num[T]+1ll*i*Cnt[i*T]%Mod)%Mod;
Mu[1]=Is[1]=1;
for(int i=2;i<=n;++i)
{
if(!Is[i]) Pri[++Tot]=i,Mu[i]=-1;
for(int j=1;j<=Tot&&i*Pri[j]<=n;++j)
{
Is[i*Pri[j]]=1;
if(i%Pri[j]==0)
{
Mu[i*Pri[j]]=0;
break;
}
Mu[i*Pri[j]]=-Mu[i];
}
}
for(int T=1;T<=n;++T)
for(int p=1;p*T<=n;++p)
Mub[T*p]=(Mub[T*p]+1ll*Mu[p]*p)%Mod;
}
inline int solve(int n)
{
int res=0;
for(int T=1;T<=n;++T)
res=(res+(ll)T*Mub[T]%Mod*Num[T]%Mod*Num[T]%Mod)%Mod;
return res;
}
signed main()
{
read(N);
for(int i=1,x;i<=N;++i) read(x),Sum=(Sum+x)%Mod,++Cnt[x],checkMax(MaxNum,x);
MaxNum=std::min(1000000,2*MaxNum);
sieve(MaxNum);Sum%=Mod;
int ans=solve(MaxNum);
ans=1ll*(ans-Sum)*inv%Mod;
write((ans+Mod)%Mod);
return 0;
}
|