Dát dohromady teorii čísel

trinerdi / icpc-notebook

The ACM-ICPC notebook of our team "Tři nerdi"

MIT License

2 stars 1 forks source link

Dát dohromady teorii čísel #54

Closed vvolhejn closed 6 years ago

vvolhejn commented 6 years ago

Různé algoritmy závisí na jiných, takže by to chtělo vybrat je tak, abychom měli i všechny závislosti.

RichardHladik commented 6 years ago

Řešeno v #67. Jediné, co jsme teď bez náhrady odebrali, je počítání modulárního inverzu v okruzích, co nejsou tělesa. Pokud to potřebujeme, jde to buď vytáhnout z modeq, nebo použít fastexp plus hledání φ(a) pro velká a. Nějakou φ-funkci tam sice máme, ale podle všeho "jen" předpočítává pro všechna a<n. V podstatě to jde převést na faktorizaci, ale to není úplně rychlé. Nápady?

RichardHladik commented 6 years ago

Asi není úplně těžké vymyslet inverzy v netělese za běhu; navíc myslím, že to ani nebudeme potřebovat. Zavírám.