LCDCT - Editorial

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

\sum_x s(x) \cdot \left(2^{c_x} - 1 \right)

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)
1 Like

How to solve for K <= 100 . Is the intended solution SOS dp with O(25* 2^25 )

2^{9}*N complexity part can be further optimised with SOS dp.
On every mask, i need to goto every submask and increase its count. So I used sos dp to solve this:
F(mask) = \sum_{}{} F(supermask)

code

I think i solved the same problem for constraints like A_i <= 10^{18} , couldnt figure out for K <= 100.

wont this give TLE?

you’re right it would, I was wondering how to solve for k<=100 as it’s mentioned in the editorial.

your solution is private, link another one

No, it isn’t - if 25 seems small enough that it could work, take K \leq 400 instead with 62 primes now (maybe take T = 1 too, though T \leq 100 will likely still run in a couple seconds in C++).

Hint

If there are p primes \leq K, there are 2^p masks to consider - but are all of them really useful?


Yeah, I was aware of this approach but chose not to enforce it because it would just be a knowledge check; meanwhile the observation that for 10^9, at most 9 primes matter and so bruteforce is fast enough was neat imo.

@iceknight1093 Can u Explain how this Happens in detail?

for k<=100;
since there are going to be atmost N * 2^9 masks (basically N * 2^9 times we are doing ++ operation in Cx array) we can iterator over those masks??

My Approach
Why is this wrong? I’ve counted the number of elements with K as the smallest prime factor , onlyK , and the number of elements with a prime less than K as the smallest prime factor (but also divisible by K) , otherThanK. Then , 2 ^(onlyK + otherThanK) gives subsets with all these elements , 2^(otherThanK) gives subsets with only those elements with a prime factor less than K , and simply subtracted them.

for 62 primes, do u mean like ncr(62 , 9) complexity

Even in nCr(62, 9) we need to choose only those subsets whose values don’t cross 1e9 hence they will be bounded by some 6e6

Can check this one:
vector cnt={1};
int step=0;
for(ll val:pr){
vector add;
for(ll value:cnt){
if(valueval<=1e9)add.pb(valueval);
step++;
}
for(auto value:add){step++;if(cnt.size()<1e7)cnt.pb(value);}
i++;
// cout<<i<<" “<<cnt.size()<<endl;
}
cout<<cnt.size()<<” "<<step<<endl;