# Sum Over Subsets Codeforces Round #678 SOLUTION

### F. Sum Over Subsets Codeforces Round #678 SOLUTION

You are given a multiset S. Over all pairs of subsets A and B, such that:
B⊂A;
|B|=|A|−1;
greatest common divisor of all elements in A is equal to one;
find the sum of ∑x∈Ax⋅∑x∈Bx, modulo 998244353.
Input
The first line contains one integer m (1≤m≤105): the number of different values in the multiset S.
Each of the next m lines contains two integers ai, freqi (1≤ai≤105,1≤freqi≤109). Element ai appears in the multiset S freqi times. All ai are different.
Output
Print the required sum, modulo 998244353.
Examples
inputCopy
2
1 1
2 1
outputCopy
9
inputCopy
4
1 1
2 1
3 1
6 1
outputCopy
1207
inputCopy
1
1 5
outputCopy
560
Note
A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.
A⊂B: Set A is a subset of a set B.
In the first example B={1},A={1,2} and B={2},A={1,2} have a product equal to 1⋅3+2⋅3=9. Other pairs of A and B don’t satisfy the given constraints.
SOLUTION :

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int mod = (int) 1e9 + 7;

int pw(int a, int b) {
int r = 1;
while (b) {
if (b & 1) {
r = (ll) r * a % mod;
}
a = (ll) a * a % mod;
b /= 2;
}
return r;
}

const int M = mod;

int add(int a, int b) {
a += b;
if (a >= M) return a – M;
if (a < 0) return a + M;
return a;
}

int mul(int a, int b) {
return a * (ll) b % M;
}

int dv(int a, int b) {
return mul(a, pw(b, M – 2));
}

int sqr(int x) {
return mul(x, x);
}

const int N = (int) 2e5 + 7;
int f[N];

int c(int n, int k) {
if (!(0 <= k && k <= n)) {
assert(0);
}
return dv(f[n], mul(f[k], f[n – k]));
}

signed main() {
ios::sync_with_stdio(0);
cin.tie(0);

///freopen (“input”, “r”, stdin);

f[0] = 1;
for (int i = 1; i < N; i++) f[i] = mul(f[i – 1], i);

int m;
cin >> m;
vector<int> a;
for (int i = 1; i <= m; i++) {
int x, f;
cin >> x >> f;
for (int j = 1; j <= f; j++) a.push_back(x);
}
int n = (int) a.size(), sol = 0;
for (int m = 1; m < (1 << n); m++) {
int g = 0;
for (int i = 0; i < n; i++) if (m & (1 << i)) g = __gcd(g, a[i]);
if (g == 1) {
vector<int> e;
int su = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (m & (1 << i)) {
e.push_back(a[i]);