Link to topic
CF direction
Luogu direction
Problem solution
First consider eliminating
g
c
d
gcd
Limitations of gcd
Consider the M?bius inversion
priority enumeration
d
d
d can be answered as
∑
d
=
1
no
mu
(
d
)
?
a
no
the s
(
d
)
\sum_{d=1}^{n}\mu(d)*ans(d)
∑d=1n?μ(d)?ans(d)
in
a
no
the s
(
d
)
ans(d)
ans(d) is all
a
i
a_i
ai? yes
d
d
Answers in multiples of d
make
a
i
a_i
ai? for
d
d
The reset of all numbers that are multiples of d is
S
S
S
consider
∑
x
∈
A
x
?
∑
the y
∈
B
the y
=
∑
x
∈
A
∑
the y
∈
B
x
the y
\sum_{x\in A}x*\sum_{y\in B}y=\sum_{x\in A}\sum_{y\in B} xy
∑x∈A?x?∑y∈B?y=∑x∈A?∑y∈B?xy
consider each pair
x
,
the y
x,y
Answers contributed by x,y
-
x
x
x with
the y
the y
y is the same number (the same number here is not the same value)
the answer isx
2
?
(
∣
S
∣
?
1
)
?
2
∣
S
∣
?
2
x^2*(|S|-1)*2^{|S|-2}
x2?(∣S∣?1)?2∣S∣?2
for the only absenceA
A
in A, but in
B
B
The numbers in B have
∣
S
∣
?
1
|S|-1
∣S∣? Choose from 1, others
∣
S
∣
?
2
|S|-2
∣S∣?2 optional
-
x
x
x with
the y
the y
y are not the same number (could be the same value)
the answer isx
the y
?
(
(
∣
S
∣
?
2
)
?
2
∣
S
∣
?
3
+
2
∣
S
∣
?
2
)
xy*((|S|-2)*2^{|S|-3} + 2^{|S|-2})
xy?((∣S∣?2)?2∣S∣?3 + 2∣S∣?2)
likex
x
x is not the only … number, then the only … number is
∣
S
∣
?
2
|S|-2
∣S∣? Choose from 2, other
∣
S
∣
?
3
|S|-3
∣S∣?3 optional
likex
x
x is the only number of … , then the other
∣
S
∣
?
2
|S|-2
∣S∣? 2 numbers are optional
consider
f
r
e
q
freq
The value range of freq is very large, consider considering each value together
classification is still the same
-
x
x
x with
the y
the y
y is the same number
A
no
the s
=
f
r
e
q
x
?
x
2
?
(
∣
S
∣
?
1
)
?
2
∣
S
∣
?
2
Ans=freq_x*x^2*(|S|-1)*2^{|S|-2}
Ans=freqxx2?(∣S∣?1)?2∣S∣?2
-
x
x
x with
the y
the y
y are not the same number (could be the same value)
continue category discussion
likex
,
the y
x,y
x, y have the same value
A
no
the s
=
f
r
e
q
x
?
(
f
r
e
q
x
?
1
)
?
x
2
?
(
(
∣
S
∣
?
2
)
?
2
∣
S
∣
?
3
+
2
∣
S
∣
?
2
)
Ans=freq_x*(freq_x-1)*x^2*((|S|-2)*2^{|S|-3} + 2^{|S|-2})
Ans=freqx(freqx1)?x2?((∣S∣?2)?2∣S∣?3 + 2∣S∣?2)
likex
,
the y
x,y
x,y values are different
makethe s
u
m
=
∑
d
∣
i
i
?
f
r
e
q
i
sum=\sum_{d|i} i*freq_i
sum=∑d∣i?i?freqi?
A
no
the s
=
f
r
e
q
x
?
x
?
(
the s
u
m
?
f
r
e
q
x
?
x
)
?
(
(
∣
S
∣
?
2
)
?
2
∣
S
∣
?
3
+
2
∣
S
∣
?
2
)
Ans=freq_x*x*(sum-freq_x*x)*((|S|-2)*2^{|S|-3} + 2^{|S|-2})
Ans=freqxx?(sum?freqxx)?((∣S∣?2)?2∣S∣?3 + 2∣S∣?2)
The actual complexity is the harmonic series
o
(
no
l
no
no
)
O(nln\;n)
O(nlnn)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N(100100),P(998244353);
int n,ans,mu[N],sum[N];
int pr[N],cnt;
bool vis[N];
inline int read(){<!-- -->
int FF=0,RR=1;
char ch = getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1) + (FF<<3) + ch-48;
return FF*RR;
}
int qmi(int a,int b){<!-- -->
if(b<0) return 0;
int res=1;
for(;b;b>>=1){<!-- -->
if(b & amp;1) res=res*a%P;
a=a*a%P;
}
return res;
}
int solve(int d){<!-- -->
int tot1=0, tot2=0;
for(int i=d;i<=100000;i + =d) tot1 + =sum[i],tot2=(tot2 + sum[i]%P*i%P)%P;
if(tot1<2) return 0;
int pw1=qmi(2,(tot1-3)%(P-1)),pw2=qmi(2,(tot1-2)%(P-1));
tot1%=P;
int res=0;
for(int i=d;i<=100000;i + =d){<!-- -->
int t=sum[i]%P;
//x, y are the same number
res=(res + t*i%P*i%P*(tot1-1 + P)%P*pw2%P)%P;
//x, y have the same value
if(sum[i]>=2) res=(res + t*(t-1 + P)%P*i%P*i%P*((tot1-2 + P)*pw1%P + pw2) %P)%P;
//x, y values are different
res=(res + t*i%P*(tot2-i*t%P + P)%P*((tot1-2 + P)*pw1%P + pw2)%P)%P;
}
return res;
}
void sieve(){<!-- -->
mu[1]=1;
for(int i=2;i<=100000;i ++ ){<!-- -->
if(!vis[i]) vis[i]=1,pr[ + + cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt & amp; & amp;pr[j]<=100000/i;j ++ ){<!-- -->
vis[pr[j]*i]=1;
if(i%pr[j]==0) break;
mu[i*pr[j]]=-mu[i];
}
}
}
signed main(){<!-- -->
n=read(),sieve();
for(int i=1,x,y;i<=n;i + + ) x=read(),y=read(),sum[x] + =y;
for(int i=1;i<=100000;i + + ) if(mu[i]) ans=((ans + mu[i]*solve(i))%P + P)%P;
printf("%lld",ans);
return 0;
}