CPP Program Find the Good Sets – Number Theory

by
  • 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