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]);su = add(su, a[i]);cnt++;}}sol = add(sol, mul(cnt – 1, sqr(su)));}}cout << sol << “n”;}