# LCMSEQ - Editorial

Setter: Seemanta Bhattacharjee
Tester: Harris Leung
Editorialist: Trung Dang

2527

# PREREQUISITES:

Combinatorics, GCD and LCM

# PROBLEM:

Given an array A of N integers. Find the number of different subsequences of the array that follow these conditions:

• For any two numbers a, b in the subsequence: lcm(l, a) - a = lcm(l, b) - b. Here, l is the length of the subsequence.
• l > 1, l is the length of the subsequence.

Since the answer can be very long, print it modulo 10^9+7.

Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. Two subsequences are considered different if one of them contains an index i that the other one doesn’t.

# EXPLANATION:

Subsequences that are consisted of a single value are always good, so let’s consider subsequences with two or more values. Let’s consider two values a and b first, and see which conditions should l have.

WLOG, let a > b. We see that lcm(a, l) - a = lcm(b, l) - b \Rightarrow l \cdot (a / gcd(a, l) - b / gcd(b, l)) = a - b, where we used the identity lcm(x, y) = x \cdot y / gcd(x, y). Therefore, l divides a - b. Let kl = a - b for some integer k, then a = b + kl, then gcd(a, l) = gcd(b + kl, l) = gcd(b, l). Let gcd(a, l) = gcd(b, l) = g, then l \cdot (a / g - b / g) = a - b \Rightarrow l = g, or l = lcm(a, l) = lcm(b, l), which means l divides both a and b.

Extending from this condition, in general, a subsequence is good iff:

• All values in the subsequence are equal, or
• Length of the subsequence divides every value in the subsequence.

The solution from here is quite simple: for case 2, for each length l from 2 to N, we count the number of values that is divisible by l (let this value be cnt_l). Then the number of possible subsequences of length l of case 2 is \binom{cnt_l}{l}; while for case 1, let the occurence of each value be occ_v, then its contribution to the answer is 2^{occ_v} - 1 - occ_v. Be careful of the overlap between case 1 and case 2.

# TIME COMPLEXITY:

Time complexity is O(N \sqrt{\max(A)}) for each test case.

# SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 1e9 + 7;
int tc, cs = 1;

string to_string(string s) {
return '"' + s + '"';
}

string to_string(const char* s) {
}

string to_string(bool b) {
return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

void debug_out() { cerr << endl; }

void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int n, a[N];
unordered_map<int, int> cnt, freq;

ll f[N], If[N], pw[N];

ll bigmod(ll a, ll n, ll M) {
ll res = 1LL;
while (n) {
if (n & 1) res = (res * a) % M;
a = (a * a) % M;
n >>= 1;
}
return res % M;
}

ll Inverse(ll n) {
return bigmod(n, mod-2, mod);
}

ll nCr(ll n,ll r) {
if (n < r) return 0;
return (((f[n] * If[r]) % mod) * If[n-r]) % mod;
}

void prec() {
f[0] = 1, If[0] = 1;
f[1] = 1, If[1] = 1;
for (int i = 2; i <= N - 10; ++i){
f[i] = (f[i-1] * 1LL * i) % mod;
If[i] = ((Inverse(i) * If[i-1]) % mod);
}
}

void test_cases() {
cnt.clear(); freq.clear();
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], freq[a[i]]++;
ll ans = 0;
for (auto p: freq) {
ll f = p.second;
ans = (ans + pw[f]) % mod;
ans = (ans - (f + 1) + mod) % mod;
for (int j = 1; j*j <= p.first; ++j) {
if (p.first % j == 0) {
cnt[j] += f;
if (j > 1) ans = (ans - nCr(f, j) + mod) % mod;
if (((p.first/j) != j) && p.first/j <= n) {
cnt[p.first/j] += f;
if (p.first/j > 1) ans = (ans - nCr(f, p.first/j) + mod) % mod;
}
}
}
}
for (int len = 2; len <= n; ++len) {
ans = (ans + nCr(cnt[len], len)) % mod;
} cout << ans << '\n';
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
prec();
pw[0] = 1;
for (int i = 1; i <= N-10; ++i) pw[i] = (pw[i - 1] * 2LL) % mod;
cin >> tc;
while (tc--) {
test_cases();
}
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
const int iu=1e7;
const int ty=1e5;
ll f[100001],inf[100001],p2[100001];
ll pw(ll x,ll y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
ll res=pw(x,y/2);
return res*res%mod;
}
ll C(ll x,ll y){
if(x<y) return 0;
return f[x]*inf[y]%mod*inf[x-y]%mod;
}
int sp[iu+1];
int pc=0;
int ps[iu+1];

int n;
int a[100001];
int f1[iu+1],f2[iu+1];

int bs=0;
int bin[iu+1];
ll ans=0;
void get(int x,int w,int king){
//cout << "get " << x << ' ' << w << ' ' << king << endl;
if(x==1){
if(++f1[w]==1) bin[++bs]=w;
if(w!=1) ans=(ans+mod-C(f2[king],w-1));
return;
}
int p=sp[x];
get(x/p,w,king);
while(x%p==0){
w*=p;x/=p;
}
//cout << x << ' ' << w << ' ' << king <<' ' << p << endl;
get(x,w,king);
}
void solve(){
cin >> n;ans=0;bs=0;
for(int i=1; i<=n ;i++){
cin >> a[i];
get(a[i],1,a[i]);
f2[a[i]]++;
}
for(int i=1; i<=bs ;i++){
int x=bin[i];
//cout << "! " << x << ' ' << f1[x] << endl;
if(x!=1) ans=(ans+C(f1[x],x))%mod;
ans=(ans+p2[f2[x]]-f2[x]-1+mod)%mod;
f1[x]=f2[x]=0;
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
f[0]=1;p2[0]=1;
for(int i=1; i<=ty ;i++) f[i]=f[i-1]*i%mod,p2[i]=p2[i-1]*2%mod;
inf[ty]=pw(f[ty],mod-2);
for(int i=ty; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
for(int i=2; i<=iu ;i++){
if(sp[i]==0){
sp[i]=i;
ps[++pc]=i;
}
for(int j=1; ps[j]<=sp[i] && ps[j]*i<=iu && j<=pc ;j++){
sp[ps[j]*i]=ps[j];
}
}
int t;cin >> t;while(t--) solve();
}

Editorialist's Solution
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

const int MX = 1E5 + 5;
using mint = modint1000000007;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
vector<mint> fct(MX);
fct[0] = 1;
for (int i = 1; i < MX; i++) {
fct[i] = fct[i - 1] * i;
}
auto C = [&](int n, int k) {
return n < k || k < 0 ? mint(0) : fct[n] / fct[k] / fct[n - k];
};
while (t--) {
int n; cin >> n;
map<int, int> occ;
vector<int> len(n + 1);
for (int i = 0; i < n; i++) {
int u; cin >> u;
occ[u]++;
}
mint ans = 0;
for (auto [val, cnt] : occ) {
ans += mint(2).pow(cnt) - 1;
for (int i = 1; i * i <= val; i++) {
if (val % i == 0 && i <= n) {
len[i] += cnt;
ans -= C(cnt, i);
if (val / i != i && val / i <= n) {
len[val / i] += cnt;
ans -= C(cnt, val / i);
}
}
}
}
for (int i = 2; i <= n; i++) {
ans += C(len[i], i);
}
cout << ans.val() << '\n';
}
}

4 Likes

after brute forcing for the some values i got the pattern but stuck in the implementation side,
i like the problem though

9 Likes

Anyone please share small example of non single value sub sequence where - lcm(a,l)−a=lcm(b,l)−b holds

A = [2, 4].

1 Like

Hey there, I want to debug my code for the test case for which I am getting Run Time Error. But it does not show up. How to proceed? Here is my submission which I am trying to debug:

https://www.codechef.com/viewsolution/68180843

I would suggest randomly generating some sample test cases that fit the constraints. That method often helps me with debugging my code.

1 Like

Why O(max(A)logn) method gets TLE?
It is equal to or even better than O(N*sqrt(max(A))).
Submission:Solution: 68191460 | CodeChef

        //count the number of case1
for(int i=0;i<sz;i++)
ans=(ans+two[cnt[v[i]]]+TMD-cnt[v[i]]-1)%TMD;
//count the number of case2
for(int i=2;i<=n;i++)
{
int tcnt=0;
for(int j=1;i*j<=mx;j++)
{
tcnt+=cnt[i*j];
//minus the overlap between case 1 and case 2
ans=(ans-C(cnt[i*j],i)+TMD)%TMD;
}
//tcnt means the number of i's multiples
ans=(ans+C(tcnt,i))%TMD;
}

1 Like

https://www.codechef.com/viewsolution/68173608, into this solution, why does this TLE ? The editorialist solution of *Nsqrt(MA)log(MA) passes, but in this solution, the time-complexity overall is MAlog(MA)(logn) which is close to the above complexity?

for (int i = 2; i <= n; i++)
{
ll cnt = 0;
for (int j = i; j <= ma; j += i)
{
if (freq.count(j))
{
cnt += freq[j];
ans -= nCr(freq[j], i);
ans %= mod;
}
}
ans += nCr(cnt, i);
ans %= mod;
}


In the above code logN is the factor due to map, while nCr also takes logMA due to modulo-inverses (see the attached link code). Besides the overall complexity by ma/2 + ma/3 + ma/4 … should sum up to *MAlog(MA)logN, which TLE’s and I am unable to understand why does this square root solution passes.

Thanks for any help.

or l = lcm(a, l) = lcm(b, l)l=lcm(a,l)=lcm(b,l), which means ll divides both aa and bb. I think in this line there should some changes, as l=gcd(a,l)=gcd(b,l) not lcm(a,l) or lcm(b,l)

4 Likes

I figured out the case 1 and after I got to case 2 no time was left. Very interesting problem though.

1 Like

damn, I came up with the solution within 15 mins but was unable to handle overlapping case, worst feeling ever

3 Likes

I’m in the same situation as you.

1 Like

In my opinion,the reason is:
In test data,max(A) is big enough(near 10^7).However,the other A[1,2,…n](except max(A)) are too small so that they can be quickly factorized(much less than O (sqrt (max(A)))).
O(max(A)logn) method’s complexity only depends on max(A) but O(n*sqrt(max(A))) method not,so it gets TLE.
In addition,we can simply use an array to count the number(a[i]<=10^7),it has less time complexity than map.

2 Likes

The time complexity should be O(N * sqrt( max(A) )*log2(1e9+7) )
mint does division in log(MOD) time

How is the editorialist’s solution dealing with overlapping problem?

Time limits were too tight I tried to submit many times using naive method to calculate divisors and also by using O(Amax*log(Amax)), I was getting TLE in both.

Why I am getting TLE?
I am doing the same thing but in different implementation.