HackerRank Number Theory – Equations

Challenge: Equations

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464737199

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/equations/problem

Cerinta

Find the number of positive integral solutions for the equations 
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{N!}$$
    
**Input Format**  
An integer N   

**Output Format**  
The number of positive integral solutions for the above equation modulo 1000007  

**Constraints**  
$1 \le N \le 10^6$  

**Sample Input00**  

	1  

**Sample Output00**  

	1

**Sample Input01**

	32327

**Sample Output01**

	656502  

**Sample Input02**

	40921

**Sample Output02**

	686720

Cod sursa

// https://www.hackerrank.com/challenges/equations

#include <iostream>

using namespace std;

#define MAX 1000010
#define MODULO 1000007

int prime[MAX] = {0}, cnt[MAX] = {0};

int main() {
    long long ans = 1LL;
    int n;

    cin >> n;

    for (int i = 2; i <= MAX /i; i ++) {
        if (!prime[i]) {
          prime[i] = i;

          for (int j = i * i ; j < MAX; j += i)
            prime[j] = i;
        }
    }

    for (int i = 2; i <= n; i ++) {
        int m = i;

        while (m > 1) {
            if (prime[m] == 0)
                prime[m] = m;

            cnt[prime[m]] += 2;
            m /= prime[m];
        }
    }

    for (int i = 0; i <= n; i ++)
        ans = ans * (1 + cnt[i]) % MODULO;

    cout << ans << endl;
    return 0;
}