CPP Program Find the Good Sets – Number Theory

  • You are given an array consisting of n distinct integers. A set s of numbers is called good if you can rearrange the elements in such a way that each element divides the next element in the order, i.e. ‘si’ divides ‘si + 1’, such that i < |s|, where |s| denotes the size of set |s|.
  • Find out a number of distinct good sets that you can create using the values of the array. You can use one value only once in a particular set; ie. a set cannot have duplicate values. Two sets are said to be different from each other if there exists an element in one set, which does not exist in the other.
  • As the answer could be large, print your answer modulo 10^9 + 7.

Input format:

  1. The first line of the input contains an integer T denoting the number of test cases. T-test cases follow.
  2. The first line of each test case contains an integer n denoting the number of elements in array a.
  3. The next line contains n space-separated integers denoting the elements of the array a.

Output format:

  1. The first line of the input contains an integer T denoting the number of test cases. T-test cases follow.
  2. The first line of each test case contains an integer n denoting the number of elements in array a.
  3. The next line contains n space-separated integers denoting the elements of the array a.

Constraints:

1 ≤ T ≤ 3
1 ≤ n ≤ 7.5 * 10^5
1 ≤ ai ≤ 7.5 * 10^5
All the elements of the array a are distinct.

Sample Input:

2
2
1 2
3
6 2 3

Sample Output:

3
5

Explanation:

Test case 1. There are three sets which are good {1}, {2}, {1, 2}.
Test case 2. There are five sets which are good {6}, {2}, {3}, {6 2}, {6, 3}.

Code:

#include <iostream> #include <math.h> #define m 1000000007 #define ll long long int using namespace std; void makeSieve(ll n) { bool *isprime = new bool[n + 1]; for (ll i = 0; i < n + 1; i++) { isprime[i] = true; } isprime[0] = false; isprime[1] = false; for (ll i = 2; i <= sqrt(n); i++) { if (isprime[i]) for (ll j = i; j * i <= n; j++) { isprime[j * i] = false; } } ll total_divisors = 1; for (ll i = 0; i < n + 1; i++) { if (isprime[i]) { ll current_sum = 0; for (ll j = 1; pow(i, j) <= n; j++) { current_sum += n / pow(i, j); } total_divisors =(total_divisors%m * (current_sum + 1)%m)%m; } } cout << total_divisors << endl; delete[] isprime; } int main() { ll t; cin >> t; while (t--) { ll n; cin >> n; makeSieve(n); } }
Code language: C++ (cpp)

Leave a Comment