| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
hey i want to calculate something i needed some attention so i wrote must read blog.
let's say i want to calculate a*b % P where 0<= a,b <= 1e9 and p = 1e9+7
how to calculate this by using only integer number i don't want to use long long as many stupid people do.
Weird that you call people that use long long stupid, but you can solve it in $$$O(\log(\min(a, b))$$$ using only addition with binary "exponentiation". The operator here that is to be applied repeatedly is addition instead of multiplication.
I am not the only one many people suggest to not use long long because it causes MLE/TLE in many problems.
Btw Where is the code?
But don't you think it is unnecessary to use a much more complex algorithm to do such a simple problem and use more time?
Sometimes i get TLE/MLE that's why i am asking.
You newbies do not practice problems that's why you don't know.
But, $$$O(\log(\min(a,b))) \gt O(1)$$$
BTW, thank you for calling me newbie in your first Rev.
Still solves MLE problem. And % Operations on long long is not O(1) i bileave
...No problem
You are right, it isn't $$$O(1)$$$. But it is still faster. And you want to write a bunch of code instead of
a*b%p.You are a newbie tooo, aren't you?
Guess my rating too.
By your rating, you can write the code yourself.
I can save it in my code snippets. I have brain
Give me code why r u wasting my time?
guess my rating and bileave on your instincts
First give me code after that i will guess
Lol i dont know that's why i have written a blog
Now, guess my rating.
You said you will guess.
MLE happens only when you store too many 64-bit integers in a data structure, or use too many 64 bit-integers in a recursive function (which contributes to stack size). The argument that they cause TLE is more or less outdated since most judges have 64-bit architecture now and the main culprit behind the TLE was slow 64-bit multiplication on 32-bit machines.
If you use the algorithm I suggested on 32-bit machines, it will be slower than 64-bit multiplication. I would have recommended you to write code for this idea yourself, but if you haven't seen binary exponentiation before, you can go through this.
i am getting too many compilation errors like
...
This will compile only with C++20. Try custom invocation on Codeforces.
ok i found my answer on google code works now Thanks
But can you explain or is there any blog which explains this code. i think i need to learn more about c++ 20.
nor
I would recommend reading on binary exponentiation from the article I linked and trying to implement it yourself. If $$$f$$$ is any associative function, calling the function
apply_n(a, n, f, base)computesf(base, f(a, f(a, ...)))whereais repeatedntimes.On a serious note, how does this perform compared to Barrett reduction/Montgomery reduction?
Pretty bad, won't recommend.