LCMSEQ - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

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) {
  return to_string((string) 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; }
 
template <typename Head, typename... Tail>
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 :smiling_face_with_tear:

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 :frowning: 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.
My submission link : Link

Did same as editorals solutions, still getting TLE
Please look into it @kuroni
Submission link : Link

My TLE solution passed by changing long long int to int. Why is the time limit so tight? Just using long long int shouldn’t be the reason for TLE, shouldn’t it?

How it runs over the given constraints?

O ( N sqrt ( max(A) ) ) => 0 ( 10^5 * sqrt(10^7) )
which results ~ O(10^8).

Pls Correct me if I am wrong.