We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

This problem is a programming version of Problem 216 from projecteuler.net

Consider three integers , and where , and is not the square of an integer.

Let the second degree polynomial . In this challenge, we will be interested in the prime values of for integers .

E.g. with , and , the first such prime numbers are , , , , , and .

How many numbers are prime for ?

Input Format

The first line of each test case contains three space-separated integers , and .
The second line contains a single integer which is the number of queries.
Each of the next lines contains a value of .

Constraints

  • .
  • .
  • .
  • .
  • and is not a perfect square.
  • .

Output Format

Print the answer to each query in a new line.

Sample Input 0

2 0 -1
1
10

Sample Output 0

7

Explanation 0

The values of for are :

Only are prime. Hence the answer is .

Sample Input 1

2 0 1
1
20

Sample Output 1

4

Explanation 1

The evaluation of for yields to :

The prime values in this list are . Therefore the answer is .

Sample Input 2

1 0 1
1
13

Sample Output 2

5

Explanation 2

There exist prime numbers of the form where : .