Equation
Time limit2sMemory limit128 MB
Given N, count triples X+Y=Z with X<=Y under three separate conditions: bounded distinct integers, divisors of N, and primes up to N.
- Level
Medium5 of 10
- Topics
- Number theory, Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
Let three positive integers (X), (Y), and (Z) satisfy the equation below.
[ X + Y = Z \quad (X \le Y) ]
Without restrictions there can be infinitely many solutions. For each of the following three conditions, applied independently, count how many solutions satisfy the equation.
- Condition A: (X), (Y), and (Z) are all at most (N), and they are pairwise distinct.
- Condition B: (X), (Y), and (Z) are all positive divisors of (N).
- Condition C: (X), (Y), and (Z) are all positive primes at most (N).
The conditions are not applied together. Compute the number of solutions separately for conditions A, B, and C.
Input
The first line contains a positive integer (N).
[ 1 \le N \le 500,000 ]
Output
Print the number of solutions under condition A on the first line.
Print the number of solutions under condition B on the second line.
Print the number of solutions under condition C on the third line.