PROBLEM LINK:
Team Divisions
Author: loud_mouth
Tester: rivalq
Editorialist: loud_mouth
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a set of non-unique numbers, how many ways to divide them into 2 sets A and B, such that, every element of A divides every element of B.
Prerequisites:
Basic Maths, Prefix sums and Implementation
EXPLANATION:
First off, to check if every element of A divides every element of B, it is enough to know LCM of A divides GCD of B. Also, clearly, every element of A <= all elements of B.So, we should sort our input and realize either no value will exist in both sets or only one. Otherwise the conditions we deduced above will fail. Try and check this for yourself.
TYPE 1 (CLEAR DIVISONS):
In the case where no value is on both sides, the constraint will be such that one prefix of the sorted values array will be in A and the rest will be team B. (otherwise, again, this will violate our deduced conditions.)
Therefore for every possible unique value, we can see if prefix LCM divides suffix GCD or not.If it does, we add 1 to the answer.
We define 2 arrays L and G where L[i] is the LCM of values(after sorting) from index 0...i (inclusive) and G[i] is the GCD of values(after sorting) from index i...n-1 (inclusive)
Note that LCM value might cause overflow, but as prefix LCM can only ever increase, we need not concern ourselves with indices where LCM[i] increases beyond 1e9, since we need LCM to divide the GCD, and the GCD for values <= 1e9 will also be <= 1e9.
Thus, for all valid i if L[i]<=1e9 and G[i+1]%L[i]==0, we add one to the answer.
TYPE 2 (UNCLEAR DIVISONS):
For the second case, where one value 'V' exists in both the teams, we iterate over all possible values. Let the frequency of this value be 'F'.
It is clear in such a case, L[i]<=1e9 and G[i]%L[i]==0 (where i is the index where V is located in the sorted array), otherwise, all elements of A will not divide all elements of B.
How many such cases will exist where some of the F values are on team A and some are on team B? Basic maths tells us the answer is 2^F-2 (we subtract two cases. One where all V values are on the left and one where all values are on the right, since they would make this a clear division and we have already counted those.)
TL;DR : we add 1 for every index where G[i+1]%L[i]==0 and 2^F-2 where G[i]%L[i]==0, where G is suffix GCD and L is prefix LCM array.
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define vi vector<ll>
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define pb push_back
#define endl '\n'
#define sa(x) sort((x).begin(), (x).end());
#define int long long
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T> static inline void sd(vector<T> &x) {sort((x).begin(), (x).end(), greater<T>()) ; }
#define ii pair<ll, ll>
#define vii vector<ii>
#define x first
#define y second
//128248098
const int mod = 998244353, N=1e5+5;
int two[N]={};
void solve(){
int n;
cin>>n;
vector<ii> v(n);
rep(i,0,n){
cin>>v[i].x>>v[i].y;
v[i].y = two[v[i].y];
}
if(n == 1){
cout << (v[0].y-1+mod)%mod << endl;
return;
}
sa(v);
int GCD[n];
int LCM[n];
GCD[n-1]=v[n-1].x;
LCM[n-1]=-1;
for(int i=n-2; i>=0; --i){
GCD[i] = __gcd(GCD[i+1], v[i].x);
LCM[i]=-1;
}
int ans=0;
for(int i=0; i<n-1; ++i){
if(i==0){
LCM[i]=v[i].x;
}
else LCM[i] = (LCM[i-1] * v[i].x)/__gcd(LCM[i-1], v[i].x);
if(LCM[i] > 1e9) {
LCM[i]=-1;
break;
}
if(GCD[i]%LCM[i] == 0){
ans += v[i].y;
ans %= mod;
}
else if(GCD[i+1]%LCM[i] == 0){
ans = (ans+1)%mod;
}
}
if(LCM[n-2]!=-1)
{
LCM[n-1] = (LCM[n-2] * v[n-1].x)/__gcd(LCM[n-2], v[n-1].x);
if(GCD[n-1]%LCM[n-1] == 0)
ans += v[n-1].y-1;
ans = (ans+mod)%mod;
}
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int testcases=1;
two[0]=0;
rep(i,1,N){
two[i] = (((two[i-1]+1)%mod)*2)%mod;
two[i]--;
if(two[i] == -1) two[i]=mod-1;
}
cin>>testcases;
while(testcases--){
solve();
}
return 0;
}
Tester's Solution
// Jai Shree Ram
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
const int MOD = 998244353;
struct mod_int {
int val;
mod_int(long long v = 0) {
if (v < 0)
v = v % MOD + MOD;
if (v >= MOD)
v %= MOD;
val = v;
}
static int mod_inv(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const {
return val;
}
mod_int& operator+=(const mod_int &other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}
mod_int& operator-=(const mod_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return x % m;
#endif
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
mod_int& operator*=(const mod_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}
mod_int& operator/=(const mod_int &other) {
return *this *= other.inv();
}
friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
mod_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
mod_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
mod_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
bool operator==(const mod_int &other) const { return val == other.val; }
bool operator!=(const mod_int &other) const { return val != other.val; }
mod_int inv() const {
return mod_inv(val);
}
mod_int pow(long long p) const {
assert(p >= 0);
mod_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &stream, const mod_int &m) {
return stream << m.val;
}
friend istream& operator >> (istream &stream, mod_int &m) {
return stream>>m.val;
}
};
int solve(){
int n;cin >> n;
vector<int>a(n+1);
map<int,int>mp;
rep(i,1,n+1){
int x;
cin >> a[i] >> x;
mp[a[i]]+=x;
}
if(n==1)
{
int f = (*(mp.begin())).second;
cout << mod_int(2).pow(f)-2 <<endl;
return 0;
}
vector<int>t={0};
int m = mp.size();
for(auto i:mp){
t.push_back(i.x);
}
vector<int>plcm(m+1,1);
for(int i = 1; i <= m; i++){
plcm[i] = plcm[i-1]*t[i]/gcd(plcm[i-1],t[i]);
if(plcm[i] > 1e9){
break;
}
}
vector<int>sgcd(m+2,0);
for(int i = m; i >= 1; i--){
sgcd[i] = gcd(t[i],sgcd[i+1]);
}
mod_int ans = 0;
bool found = 0;
for(int i = 1; i + 1<= m; i++){
if(plcm[i] > 1e9){
found = 1;
break;
}
// 1...i ,i...m
if(sgcd[i]%plcm[i]==0){
ans += mod_int(2).pow(mp[t[i]])-1;
}
// 1...i , i+1..m
else if(sgcd[i+1]%plcm[i]==0){
ans++;
}
// cout<<t[i]<<" "<<ans<<endl;
}
// cout<<sgcd[m]<<" and "<<plcm[m]<<endl;
if(!found and sgcd[m]%plcm[m]==0){
ans += mod_int(2).pow(mp[t[m]])-2;
// cout<<mp[t[m]]<<endl;
}
cout << ans << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
TIME COMPLEXITY
sorting, prefix lcm, and suffix gcd will take O(n*logn). pre-calculating 2^f for all possible f will take O(MAX_FREQ).