How to calculate this thing. [MUST READ BLOG]

Блог пользователя Boring_Day

Автор Boring_Day, история, 19 месяцев назад, По-английски

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.

calculation, recalculation, must to read, hard

Boring_Day
19 месяцев назад
21

Комментарии (16)

Показать архивные | Написать комментарий?

nor

19 месяцев назад, # |

+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.

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

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

→ Ответить

LyricaIIy

19 месяцев назад, # ^ |

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?

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

← 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.

→ Ответить

LyricaIIy

19 месяцев назад, # ^ |

← Rev. 2 →

But, $$$O(\log(\min(a,b)))>O(1)$$$

Spoiler

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

← Rev. 2 →

-7

Still solves MLE problem. And % Operations on long long is not O(1) i bileave

Spoiler

→ Ответить

LyricaIIy

19 месяцев назад, # ^ |

← Rev. 3 →

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.

Spoiler

By your rating, you can write the code yourself.

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

← Rev. 3 →

I can save it in my code snippets. I have brain

Give me code why r u wasting my time?

Spoiler

Lol i dont know that's why i have written a blog

→ Ответить

LyricaIIy

19 месяцев назад, # ^ |

← Rev. 3 →

Spoiler

int 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.

→ Ответить

nor

19 месяцев назад, # ^ |

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.

Code

template <class T>
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);
}

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

← Rev. 2 →

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)::<lambda(int, int)>, int)'
   18 |         [](int x, int y) { return (x += y) >= mod ? x - mod : x; }, 0);
      |                                                                      ^
/tmp/Q0ydc4zTHf.cpp:6:3: note: candidate: 'template<class T, class auto:1> 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 <iostream>
using namespace std;

template <class T>
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;
}

→ Ответить

nor

19 месяцев назад, # ^ |

This will compile only with C++20. Try custom invocation on Codeforces.

→ Ответить

Boring_Day

19 месяцев назад, # ^ |

← Rev. 3 →

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

→ Ответить

nor

19 месяцев назад, # ^ |

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.

→ Ответить