### Boring_Day's blog

By Boring_Day, history, 6 months ago,

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.

• -50

 » 6 months ago, # |   +22 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.
•  » » 6 months ago, # ^ |   -14 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?
•  » » » 6 months ago, # ^ |   +7 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?
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   -7 Sometimes i get TLE/MLE that's why i am asking.You newbies do not practice problems that's why you don't know.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +7 But, $O(\log(\min(a,b)))>O(1)$ SpoilerBTW, thank you for calling me newbie in your first Rev.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   -7 Still solves MLE problem. And % Operations on long long is not O(1) i bileave Spoiler...No problem
•  » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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 guessLol i dont know that's why i have written a blog
•  » » » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   +2 Spoilerint cal(int a,int b,int p=1000000007){ if (b==0){ return 0; } else{ if (b&1){ return (2*cal(a,(b-1)/2,p)%p+a)%p; } return 2*cal(a,b/2,p)%p; } } You can also use addition instead of *2. Now, guess my rating.You said you will guess.
•  » » » » » » » » » 6 months ago, # ^ |   0 it's log(b).where is log(min(a,b))? Spoiler... 1567 xD
•  » » » » » » » » » 6 months ago, # ^ |   0 if (a
•  » » » » » » » » » 6 months ago, # ^ |   0 I am so dumb lolbtw what's the absolute difference between your rating and my prediction.
•  » » » » » » » » » 6 months ago, # ^ |   0 $25$. It's a nice guess.
•  » » » 6 months ago, # ^ |   +8 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. Codetemplate T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { while (n) { if (n & 1) base = f(base, a); if (n >>= 1) a = f(a, a); } return base; } constexpr int mod = 1e9 + 7; int mul_mod(int a, int b) { if (a < b) std::swap(a, b); return apply_n( a, (unsigned)b, [](int x, int y) { return (x += y) >= mod ? x - mod : x; }, 0); } 
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 i am getting too many compilation errors like Spoiler... tmp/Q0ydc4zTHf.cpp:6:21: error: 'std::unsigned_integral' has not been declared 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ^~~~~~~~~~~~~~~~~ /tmp/Q0ydc4zTHf.cpp:6:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts' 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ^~~~ /tmp/Q0ydc4zTHf.cpp:6:44: error: two or more data types in declaration of 'n' 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ^ /tmp/Q0ydc4zTHf.cpp:6:45: error: expected ')' before ',' token 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ~ ^ | ) /tmp/Q0ydc4zTHf.cpp:6:45: error: expected ';' before ',' token 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ^ | ; /tmp/Q0ydc4zTHf.cpp: In function 'int mul_mod(int, int)': /tmp/Q0ydc4zTHf.cpp:18:70: error: no matching function for call to 'apply_n(int&, unsigned int, mul_mod(int, int)::, int)' 18 | [](int x, int y) { return (x += y) >= mod ? x - mod : x; }, 0); | ^ /tmp/Q0ydc4zTHf.cpp:6:3: note: candidate: 'template T apply_n(...)' 6 | T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { | ^~~~~~~ /tmp/Q0ydc4zTHf.cpp:6:3: note: template argument deduction/substitution failed: /tmp/Q0ydc4zTHf.cpp:18:70: note: couldn't deduce template parameter 'T' 18 | [](int x, int y) { return (x += y) >= mod ? x - mod : x; }, 0); | ^  code// Online C++ compiler to run C++ program online #include using namespace std; template T apply_n(T a, std::unsigned_integral auto n, auto&& f, T base) { while (n) { if (n & 1) base = f(base, a); if (n >>= 1) a = f(a, a); } return base; } constexpr int mod = 1e9 + 7; int mul_mod(int a, int b) { if (a < b) std::swap(a, b); return apply_n( a, (unsigned)b, [](int x, int y) { return (x += y) >= mod ? x - mod : x; }, 0); } int main() { // Write C++ code here cout << mul_mod(2, 3); return 0; } 
•  » » » » » 6 months ago, # ^ |   0 This will compile only with C++20. Try custom invocation on Codeforces.
•  » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 ok i found my answer on google code works now ThanksBut can you explain or is there any blog which explains this code. i think i need to learn more about c++ 20.nor
•  » » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » » » 6 months ago, # ^ |   0 Thanks so much
•  » » 6 months ago, # ^ |   -13 On a serious note, how does this perform compared to Barrett reduction/Montgomery reduction?
•  » » » 6 months ago, # ^ |   +8 Pretty bad, won't recommend.