| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
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)))>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.