PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ro27
Preparation: iceknight1093
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
The inclusion-exclusion principle, bitmasking
PROBLEM:
The LCD of a sequence of integers is the smallest integer greater than 1 that divides them all (or 1, if no such integer exists).
Given an array A and an integer K, count the number of non-subsequences of A whose LCD is K.
EXPLANATION:
First, observe that if the LCD of some sequence isnât 1, it must be a prime number.
Why?
This follows from the more general fact that the smallest non-1 divisor of any positive integer should be prime.
If d is a divisor of N and d \gt 1, observe that any divisor of d will also divide N.
So, if d is not prime, d will have some divisor d_2 thatâs strictly less than it (and also greater than 1), which is also a divisor of N.
So, a non-prime d cannot be the smallest non-1 divisor of N.
So, if K is not a prime, the answer is immediately 0.
Now, we need to count the number of subsequences such that K is the smallest prime that divides every element of the subsequence.
So, letâs look at only those elements that are multiples of K - after all taking any other element into the subsequence isnât possible.
Suppose the count of such elements is c_K.
The number of non-empty subsequences that can be chosen is exactly 2^{c_K} - 1.
All of these subsequences will have K as a common prime factor, yes - however, some of them might have primes less than K as a common factor; so their LCDs will in fact be less than K.
We need to subtract the number of such sequences.
So, for each prime p \lt K, we can do something similar: find the number of elements that are multiples of both p and K (effectively, multiples of pK), and subtract the number of non-empty subsequences from the answer.
But now, if two primes \lt K divide a subsequence, it wouldâve been subtracted out twice, so it needs to be added back in.
But then if three primes \lt K divide a subsequence, it wouldâve been added in one time extra, so it needs to be subtracted, but then if four primesâŠ
This seems a bit annoying to deal with, but can in fact be formalized by the quite well-known inclusion-exclusion principle, in a manner thatâs also simple to implement.
Let c_x denote the number of elements of A that are multiples of x.
Notice that for the purposes of this problem, we only care about those x that are the products of distinct primes, all of which are \leq K.
Then, the inclusion-exclusion principle tells us that the answer is exactly
where the sum x is taken across all possible products of distinct primes \leq K (though x must include K), and s(x) is defined as:
- s(x) = 1 if x is the product of an odd number of primes.
- s(x) = -1 otherwise.
(You may notice that this is just the negated Möbius function, though we arenât really using any of its properties here).
We have a solution now, but it still needs to be translated into code.
For this, observe that there are only 17 primes below 60.
So, the product of a distinct number of them can be represented as a bitmask (of 17 bits), denoting which of the primes are present in the product.
Next, we need to compute the c_x values: the number of elements divisible by x, for each x.
To do that, letâs use factorization instead.
For each A_i, weâll add 1 to each of its factors that consists of distinct primes \leq K.
How to do this fast?
Once again, we can use bitmasks.
As we noted, there are 17 primes below 60.
So, iterate through them all, and find out which of them divide A_i.
This will give you some set of primes: for example, if A_i = 110292 = 2^cdot 3\cdot 7\cdot 13\cdot 101, the set of primes you obtain will be \{2, 3, 7, 13\} (101 can be ignored since itâs larger than 60).
This set \{2, 3, 7, 13\} corresponds to some bitmask of ours, say m_i.
All that needs to be done now, is to add 1 to the value of c_x, for each x thatâs a submask of m_i: this just means that A_i contributes 1 to the values of the products 2, 3, 7, 13, 2\cdot 3, 2\cdot 7, \ldots, 3\cdot 7\cdot 13, 2\cdot 3\cdot 7\cdot 13, which is exactly what we want!
Note that since A_i \leq 10^9, A_i can have at most 9 distinct prime factors.
So, there are at most 2^9 = 512 submasks we care about, and iterating through them is fast enough.
If youâre unfamiliar with iterating through submasks of a fixed bitmask, this page will be helpful.
Now that each c_x is known, the sum \sum_x s(x) \cdot \left(2^{c_x} - 1 \right) is easily computed by just directly iterating through all 2^{17} bitmasks (though ignoring any that include primes \gt K, or donât include K).
Notice that s(x) is easily computed from the bitmask corresponding to x (by looking at the number of set bits), so factorization (or ever explicitly multiplying out primes) is completely unnecessary!
Challenge: Try solving this problem for K \leq 100.
TIME COMPLEXITY:
\mathcal{O}(2^9\cdot N + 2^{17}) per testcase, and \mathcal{O}(2^9 \cdot \sum N + 2^{17}\cdot T) overall, which is fast enough because \sum N \leq 2\cdot 10^5 and T \leq 100.
CODE:
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
const int N = 17;
const int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
int cnt[(1<<N)];
int power(int a,int b)
{
if(b==0)
return 1;
else
{
int x=power(a,b/2);
int y=(x*x)%MOD;
if(b%2)
y=(y*a)%MOD;
return y;
}
}
void solve(int tc)
{
int n,k;
cin >> n >> k;
int pos = -1;
for(int i=0;i<N;i++)
if(primes[i]==k)
pos=i;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
if(pos==-1)
{
cout << 0 << '\n';
return;
}
int ans=1;
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++)
{
int m=0;
if(a[i]%k==0)
{
ans *= 2;
ans %= MOD;
while(a[i]%k==0)
a[i]/=k;
}
else
continue;
for(int j=0;j<pos;j++)
{
if(a[i]%primes[j]==0)
m|=(1<<j);
}
for(int s=m;s;s=(s-1)&m)
cnt[s]++;
}
for(int i=1;i<(1<<pos);i++)
{
int par=0;
for(int j=0;j<pos;j++)
{
if(i&(1<<j))
par^=1;
}
if(par)
ans = (ans+MOD-power(2,cnt[i])+1)%MOD;
else
ans = (ans+MOD+power(2,cnt[i])-1)%MOD;
}
ans=(ans+MOD-1)%MOD;
cout << ans << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
mod = 10**9 + 7
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
if k not in primes:
print(0)
continue
ct = [0]*(1 << 17)
for x in a:
mask = 0
for i in range(17):
if x%primes[i] == 0: mask |= 1 << i
sub = mask
while sub > 0:
ct[sub] += 1
sub = (sub - 1) & mask
ans = 0
which = 0
for i in range(17):
if primes[i] == k: which = i
for mask in range(1 << 17):
if ~mask & (1 << which): continue
if mask >= (2 << which): continue
mul = bin(mask).count('1') % 2
if mul == 1: ans += pow(2, ct[mask], mod) - 1
else: ans -= pow(2, ct[mask], mod) - 1
print(ans % mod)