Amicable numbers
Amicable numbers
Natural numbers \(A\) and \(B\) are called amicable numbers if \(B\) is equal to the sum of all proper divisors of \(A\) (divisors excluding \(A\) itself), and \(A\) is equal to the sum of all proper divisors of \(B\) (excluding \(B\) itself).
For example, numbers 220 and 284 are amicable
You are given a natural number \(M\) and \(M\) queries. Each query consists of a number \(n_i\). For each query, answer: how many pairs of amicable numbers exist such that both numbers in the pair are not greater than \(n_i\)?
Input:
- The first line contains the natural number \(M\).
- The next \(M\) lines each contain one natural number \(n_i\).
Output:
- For each query, print the number of amicable pairs on a new line.
Constraints:
- \(1 \leq M \leq 10^5\)
- \(1 \leq n \leq 10^5\)
If this task is too hard for you, try solving it when * \(m = 1\) and \(n \leq 10^5\)
Or, if it’s still too hard, try solving it when * \(m = 1\) and \(n \leq 3000\)
Example:
Input:
1
2700Output:
2