Solving problem in Field-Extension

Revision en12, by rareone0602, 2019-05-23 17:08:27

Hello Codeforcers! As a student of department of mathematics, I'd like to demonstrate an application of Extended Field.

First we should include the idea of splitting field, a splitting field F of a polynomial P is the smallest field such that

I use the word "smallest" with the sense that if P split over E implies .

In the other word, P decomposes into linear factor under it's splitting field.

For example:

  1. P = x2 + 1 does not split over but split over where which is widely used as complex.

  2. Let p = 998244353 = 7 * 17 * 223 + 1, P = x224 - 1 does not split over but split over where . The multiplication order ord(w2) = 223.

  3. Let $p =

The problem to be demonstrated is 718C - Sasha and Array.

In the problem, we should handle Fibonacci number 1, 1, 2, 3, 5, 8, ... with the formula

Unable to parse markup [type=CF_TEX]

Once a splitting field implementation is done, we can FFT under module more than

Tags #number theory, #math, polynomials

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en26 English rareone0602 2019-05-23 19:14:45 1
en25 English rareone0602 2019-05-23 19:08:03 0 (published)
en24 English rareone0602 2019-05-23 19:06:10 44
en23 English rareone0602 2019-05-23 18:51:14 36 Tiny change: ';\n~~~~~\n\n\n\nFFT\' -> ';\n~~~~~\nMy submission: [submission:54522918]\n\n\nFFT\'
en22 English rareone0602 2019-05-23 18:49:59 25 Tiny change: 'FFT\n---\nSince FFT n' -> 'FFT\n---\nAs the second example, since FFT n'
en21 English rareone0602 2019-05-23 18:46:39 127
en20 English rareone0602 2019-05-23 18:35:23 274
en19 English rareone0602 2019-05-23 18:18:10 366
en18 English rareone0602 2019-05-23 17:55:11 122
en17 English rareone0602 2019-05-23 17:51:33 21
en16 English rareone0602 2019-05-23 17:49:48 634
en15 English rareone0602 2019-05-23 17:34:23 2031
en14 English rareone0602 2019-05-23 17:20:18 104
en13 English rareone0602 2019-05-23 17:14:46 235
en12 English rareone0602 2019-05-23 17:08:27 3
en11 English rareone0602 2019-05-23 17:07:40 147
en10 English rareone0602 2019-05-23 16:56:31 92
en9 English rareone0602 2019-05-23 16:52:53 26
en8 English rareone0602 2019-05-23 16:50:39 95
en7 English rareone0602 2019-05-23 16:48:39 362
en6 English rareone0602 2019-05-23 16:32:08 114
en5 English rareone0602 2019-05-23 16:28:30 94
en4 English rareone0602 2019-05-23 16:25:27 373
en3 English rareone0602 2019-05-23 00:54:58 38
en2 English rareone0602 2019-02-03 13:05:57 36
en1 English rareone0602 2019-02-03 05:10:44 163 Initial revision (saved to drafts)