CCO Preparation Test 3 - Primitive Pythagorean Pairs

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Do you know the Pythagorean theorem? Definitely yes. Do you know Pythagorean triples? Maybe not. Do you know primitive Pythagorean pairs? Definitely not, because Bruce has not defined it yet! Let's start from Pythagorean triples. A Pythagorean triple consists of three positive integers a, b, and c, such that a^2 + b^2 = c^2. If a and b are also coprime, the pair (a, b) is named a primitive Pythagorean pair, like (3, 4). Bruce will tell you how to generate primitive Pythagorean pairs. Given two positive integers m and n (m>n), if m and n are coprime and m-n is odd, a primitive Pythagorean pair (a, b) can be calculated by a=m^2-n^2 and b=2 \times m \times n. There are an infinite number of primitive Pythagorean pairs.

Now Bruce has N cards, each of which has a positive integer v_i (i=1,2,\ldots,N). He wants to pick up a number of cards so that there are no primitive Pythagorean pairs among the selected cards. Could you please help Bruce to get the total number of different selections? Two selections are different if and only if one card is in one selection, but is not in the other selection. Bruce has to select at least one card in each selection.

Input Specification

The first line of input will consist of one integer, N, the number of cards Bruce has.
The second line of input will consist of N positive integers v_1, v_2, \ldots, v_N, where v_i is the value of card i (1 \leq i \leq N).
In 30\% of the test cases, 1 \leq v_i \leq 3\,000.
In 30\% of the test cases, 1 \leq v_i \leq 200\,000.
In 40\% of the test cases, 20\,000 \leq v_i \leq 1\,000\,000.
In 100\% of the test cases, 1 \leq N \leq 1\,000\,000.

Output Specification

Output one integer, the number of different selections modulo 10^9+7.

Sample Input

5 12 35 5

Sample Output


Explanation of Output for Sample Input

There are two primitive Pythagorean pairs (5, 12) and (12, 35). So, there are 8 different selections: \{5\}, \{12\}, \{35\}, \{5\}, \{5, 35\}, \{35, 5\}, \{5, 5\}, \{5, 35, 5\}.


  • 0
    justin_g_20  commented on Oct. 18, 2020, 2:06 a.m.

    will dmoj conjoin the subtasks together?

  • -1
    ilex  commented on May 20, 2017, 3:39 a.m.

    Are the tests sorted as is given in the Input specification section? I mean the first 3 tests have v_i <= 3000, second 3 have v_i <= 200000 and so on?

  • 1
    zzh8829  commented on April 18, 2015, 1:02 p.m.

    what's vi for 100% case

    • 7
      fifiman  commented on April 18, 2015, 1:08 p.m.

      Its split into 3 parts:

      In 30% of the test cases, 1≤vi≤3000.

      In 30% of the test cases, 1≤vi≤200000.

      In 40% of the test cases, 20000≤vi≤1000000.

      • 3
        FatalEagle  commented on April 18, 2015, 2:51 p.m.

        +1, this is correct.