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

SpoilerBTW, 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

Spoiler...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`

.SpoilerYou 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?

Spoilerguess 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

SpoilerNow, guess my rating.

You said you will guess.

it's log(b).

where is log(min(a,b))?

Spoiler... 1567 xD

I am so dumb lol

btw what's the absolute difference between your rating and my prediction.

$$$25$$$. It's a nice 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.

Codei am getting too many compilation errors like

Spoiler...

codeThis 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)`

computes`f(base, f(a, f(a, ...)))`

where`a`

is repeated`n`

times.Thanks so much

On a serious note, how does this perform compared to Barrett reduction/Montgomery reduction?

Pretty bad, won't recommend.