Very Big Mod - Codeforces

Блог пользователя oursaco

Very Big Mod

Автор oursaco, история, 5 лет назад, По-английски

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.

oursaco
5 лет назад
10

Комментарии (10)

Написать комментарий?

Ritwin

5 лет назад, скрыть # |

← Rev. 2 →

+24

I used a Python snippet to find these examples:

$$$542110 \cdot 2^{64} + 1 = 10000164429798685026549761$$$ $$$1192092895510222934 \cdot 2^{23} + 1 = 10000000000020220185935873$$$ $$$1192092895510222937 \cdot 2^{23} + 1 = 10000000000020220211101697$$$

And for fun, I have this one as well:

$$$10002400000000000000000001$$$

It's easy enough to find such examples with sympy.isprime.

→ Ответить

oursaco

5 лет назад, скрыть # ^ |

Thanks!

→ Ответить

SilentVisitor

5 лет назад, скрыть # ^ |

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).

→ Ответить

Wind_Eagle

5 лет назад, скрыть # ^ |

Yes, there is a way.

→ Ответить

Ritwin

5 лет назад, скрыть # ^ |

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.

→ Ответить

SilentVisitor

5 лет назад, скрыть # ^ |

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?

→ Ответить

oursaco

5 лет назад, скрыть # ^ |

https://codeforces.me/contest/1656/problem/H In this problem, even inputting the numbers would cause ll overflow.

→ Ответить

timreizin

5 лет назад, скрыть # ^ |

+13

In C++ you can use __int128. Also isn't bigint in python incredibly slow and you would better not use it in ntt?

→ Ответить

Ritwin

5 лет назад, скрыть # ^ |

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.

→ Ответить