# 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.

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:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```#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)```