|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | How to divide over non prime modulo | andreyDagger`~ | 1749. Периодическая сумма | 15 янв 2023 02:26 | 1 | | | Is it possible to solve this problem without long arithmetic? | bsu.mmf.team | 1749. Периодическая сумма | 23 май 2010 07:14 | 5 | If no, please, tell me, where can I find class BigInteger. Such one, that I wrote myself, works too slow :( I think it's possible to solve it without BigNum.The question asks you to mod m...so it can't be over m Yes, but the number p can be too big, and it's impossible to calculate the answer faster, than O(n^2), where n = [lg(p)], i.e. it is a very slow method. Does anybody know faster one?
Edited by author 20.03.2010 02:31 It is possible to solve this problem in O(lg(p) * ln(n)).
And you don't need long arithmetic, just do all the computations modulo p. 64 bit integer is enough in this case. It can be even solved in O( lg(p) + ln(n) ) |
|
|
|
