I've been working on an NTT implementation, which needs a big modulo in the form of x*2^k + 1. Does anyone know any mods of this form around 1e25. I rly don't want to use Chinese remainder theorem T-T.
I've been working on an NTT implementation, which needs a big modulo in the form of x*2^k + 1. Does anyone know any mods of this form around 1e25. I rly don't want to use Chinese remainder theorem T-T.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
I used a Python snippet to find these examples:
And for fun, I have this one as well:
It's easy enough to find such examples with
sympy.isprime.Thanks!
Is there any way to implement it in other programming languages? Problem setters say that they are not biased towards any languages (Like giving any constraint which a programming language cannot compile or handle).
Yes, there is a way.
The main difficulty in this (at least in my opinion) is not testing primality, for which Miller-Rabin is very common, but the requirement of a BigInteger library.
In Python and Java, BigIntegers are built in.
In Rust, it's easy to find a package that gives BigInteger support to find these numbers on your own computer, but afaik you can't use it in a solution since I believe codeforces compiles rust with rustc and not cargo.
In C++, you can probably find biginteger libraries, which shouldn't be too hard, though I don't know any.
In your experience of competitive programming, have you encountered any problem (Particularly on Codeforces or Atcoder) which required primality testing with a very big Constraint like 2e18 or smth?
https://codeforces.com/contest/1656/problem/H In this problem, even inputting the numbers would cause ll overflow.
In C++ you can use __int128. Also isn't bigint in python incredibly slow and you would better not use it in ntt?
However in Miller-Rabin when testing the primality of some $$$n$$$, you need to multiply two numbers of size around $$$n$$$ (specifically, you need to repeatedly calculate $$$a^2 \bmod n$$$), and multiplying two numbers around $$$10^{25}$$$ gives you a result around $$$10^{50}$$$. C++'s $$$\scriptsize\texttt{__int128}$$$ can only store numbers up to $$$3.4 \times 10^{38}$$$, so this is not viable.
Yes, Python is slow, I should have mentioned that above. I'm not sure how much it could be optimized with numpy (on online judges that have support, like Atcoder I believe).
Here's a problem (not in a contest though) that required $$$\scriptsize\texttt{__int128}$$$ since the inputs went up to the max $$$\scriptsize\texttt{long long}$$$ capacity. I'll tag SilentVisitor since they asked about it too. However I haven't seen any problem with larger inputs than this.
Well, you can multiply two numbers too big to fit in the type by some modulo same way you find a (power of a number) too big to fit in the type