Primes and moduli P45675


Statement
 

pdf   zip

html

Let pn be the nth prime number (starting at 0): p0 = 2, p1 = 3, p2 = 5, p3 = 7, … Define rn as the remainder of (pn + 1 ) n + (pn − 1 )n modulo (pn)2. For instance, r3 = 42, because

(7+1)3 + (7−1)3   =   512 + 216   =   728   =   14 · 49 + 42   .

Given two integer numbers a and b, find the largest ri such that i ∈ [ a, b ].

Input

Input consists of several cases, each one with two integer numbers a and b, where 0 ≤ ab and pb ≤ 107.

Output

For every case, print the largest ri such that i ∈ [ a, b ].

Public test cases
  • Input

    1 1
    2 2
    1 2
    3 3
    1 10
    1 100
    1 1000
    600000 600002
    

    Output

    6
    2
    6
    42
    522
    107118
    15822162
    10752590320954
    
  • Information
    Author
    Albert Graells
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setè Concurs de Programacio de la UPC - Semifinal
    Date
    2009-06-29