CF1436F Sum Over Subsets

, , ,

Description

https://www.luogu.com.cn/problem/CF1436F

Solution

令 $s=\sum _{x\in A} x$ 观察到那个贡献形式为 $(|A|-1)s^2$。

考虑容斥，将**$\gcd$恰好为 $1$** 转化为 $\gcd$ 至少为 $k$ 的倍数。

令 $f_k$ 为 $\gcd$ 恰好为 $k$ 的贡献，$g_k$ 为 $\gcd$ 为 $k$ 的倍数的贡献，因为有 $g_k=\sum\limits_{k|t}f_t$，根据莫比乌斯反演有 $f_k=\sum\limits_{k|t} g_t\mu(\dfrac{t}{k})$。

现在只需要计算 $g_k$。把能被 $k$ 整除的数字拎出来。

发现如果递推去计算那个贡献形式是不好算的，需要组合数什么的。贡献形式实际上是 $\sum xy,x\in A,y\in B$，考虑直接计算每一对数的贡献，记元素总数为 $c$ ，根据 $x$ 是否等于 $y$ 讨论：

  • $x=y$ ，则 $x$ 存在于 $A,B$ 集合中，选出一个在 $A$ 但是不在 $B$ 中的数有 $c-1$ 种方案，其他可选可不选有 $2^{c-1}$。
  • $x\not = y$ ，讨论 $x$ 在不在 $B$ 种，总贡献是 $(c-2)2^{cnt-3}+2^{cnt-2}$。

然后直接计算，快速幂不预处理也能过。

注意到 $c$ 即存在直接相乘，有存在于指数中，所以不能随意取模。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=998244353;
int power(int x,int y=mod-2) {
	int sum=1;y%=(mod-1);
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
void add(int &x,int y) {x=(x+y)%mod;}
vector<pair<int,int> >O[maxn];
int n,ans;
pair<int,int>a[maxn];
int mu[maxn],prime[maxn],vis[maxn],cnt;
int calc(int k) {
	int cnt=0,res=0,sum=0,anss=0;
	for (auto x:O[k]) cnt+=x.se,add(sum,x.fi*x.se%mod),add(res,x.fi*x.fi%mod*x.se%mod);
	sum=sum*sum%mod;
	if (cnt>=2) add(anss,(cnt-1)%mod*res%mod*power(2,cnt-2)%mod);
	if (cnt>=3) add(anss,(cnt-2+mod)%mod*(sum-res+mod)%mod*power(2,cnt-3)%mod);
	if (cnt>=2) add(anss,(sum-res+mod)*power(2,cnt-2)%mod);
//	gdb(k,anss,res,sum,cnt);
	return anss;
} 
void getprime(int n) {
	vis[1]=mu[1]=1;int i,j;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i,mu[i]=-1;
		for (j=1;j<=cnt&&prime[j]*i<=n;j++) {
			vis[i*prime[j]]=1;
			mu[i*prime[j]]=-mu[i];
			if (i%prime[j]==0) {mu[i*prime[j]]=0;break;}
		}
	}
	for (i=1;i<=n;i++) if (mu[i]!=0&&(int)O[i].size()) {
//		gdb(i,O[i].size(),mu[i]);
		int res=calc(i);
		if (mu[i]==1) add(ans,res);
		else add(ans,mod-res);
	}
} 
signed main(void){
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i].fi),read(a[i].se);
	for (i=1;i<=n;i++) {
		int x=a[i].fi;
		for (j=1;j*j<=x;j++) if (x%j==0) {
			O[j].push_back(a[i]);
			if (j*j!=x) O[x/j].push_back(a[i]);
		}
	}
	getprime(1e5);
	printf("%lld",ans);
	return 0;
}