primitive rootprimitive rootprimitive rootprimitive rootHello, Codeforces users. I started to learn NTT (i already know FFT and can implement it). But my code is not working for 998244353, but it works well for smaller modules, like 7340033 and 65537.↵
↵
Here is my code: https://paste.ubuntu.com/p/QdKYCPMx3F/↵
↵
P stands for power of 2. For example: 998244353 = 119 * 2 ^ 23 + 1. R stand for primitive root.↵
↵
UPD:↵
↵
Problem was in primitive root, for module 998244353 primitive root is 3, so powers of 3 goes through all values from 1 to 998244352 in some order. But in my implementation i needed such R that powers of R goes through all values from 1 to 2^23. In order to perform this i need to take 3^119 as R.
↵
Here is my code: https://paste.ubuntu.com/p/QdKYCPMx3F/↵
↵
P stands for power of 2. For example: 998244353 = 119 * 2 ^ 23 + 1. R stand for primitive root.↵
↵
UPD:↵
↵
Problem was in primitive root, for module 998244353 primitive root is 3, so powers of 3 goes through all values from 1 to 998244352 in some order. But in my implementation i needed such R that powers of R goes through all values from 1 to 2^23. In order to perform this i need to take 3^119 as R.
