Monic irreducible polynomials P64196


Statement
 

pdf   zip

html

Here, we consider polynomials in Fp[x], that is, polynomials on x whose coefficients are elements of Fp={0, 1, 2, …, p−1}, where p is a prime number.

A polynomial is monic if the coefficient of its term with largest degree is 1. A polynomial is irreducible if it cannot be written as the product of two polynomials of smaller degree. Your task is to count the number of monic, irreducible polynomials of Fp[x] of a given degree d.

Too difficult? Do not despair! The problem is not so hard, once you know that, in Fp[x], every monic polynomial can be written in a unique way as a factor of monic, irreducible polynomials. For instance, in F2[x] there are 4 monic polynomials of degree 2 (in F2[x], all polynomials are monic), but only one of them is irreducible:

x2 = x· x                 x2+1 = (x+1)·(x+1)        x2+x = x· (x+1)           x2+x+1 =   ???

In F2[x], there are 8 monic polynomials of degree 3, but only two of them are irreducible:

     
x3x· x · x                          x3 + x2x· x· (x+1)                
x3+1= (x+1)·(x2+x+1)                     x3+x2+1=   ???                       
x3 + xx· (x+1)· (x+1)               x3 + x2 + xx· (x2+x+1)               
x3+x+1=   ???                          x3+x2+x+1= (x+1)·(x+1)·(x+1)        

Input

Input consists of several cases, each with a prime number 2 ≤ p ≤ 30 and an integer number 2 ≤ d ≤ 30. Additionally, we have pd < 109.

Output

For every case, print the number of monic, irreducible polynomials in Fp[x] of degree d.

Public test cases
  • Input

    2 2
    2 3
    2 4
    2 30
    3 2
    3 3
    3 4
    3 19
    29 6
    

    Output

    1
    2
    3
    35790267
    3
    8
    18
    61171656
    99133020
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setè Concurs de Programacio de la UPC - Final
    Date
    2009-09-16