DOUBT IN BASIC PROPERTIES OF OPERATORS PLEASE HELP!

general
, ,
1

I WANT TO ASK IF THESE TWO PIECES OF CODE WILL GIVE ME SAME RESULT OR NOT??

FIRST
ans = ((ans % M) * (phi(i) % M)) % M;
ans = ((ans % M) * (phi(n / i) % M)) % M;

SECOND

        ans = (ans % M  * phi(i) % M) % M;
        ans = (ans % M  * phi(n / i) % M ) % M;

PHI IS THE EULER TOTIENT FUNCTION

IMO THESE BOTH SHOULD GIVE ME SAME OUTPUT BUT THEY DOINT
CAN ANYONE PLEASE EXPLAIN WHY THIS IS HAPPENING???

2

In general, the expressions

((a % M) * (b % M) ) % M

and

(a % M * b % M ) % M

are not equivalent in C++ due to overflow, as the follows simple example demonstrates:

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    const int64_t a = 10;
    const int64_t b = std::numeric_limits<int64_t>::max() - 1;
    const int64_t M = 1'000'000'007;

    const int64_t ans1 = ((a % M) * (b % M) ) % M;
    const int64_t ans2 = (a % M * b % M ) % M;

    cout << "ans1: " << ans1 << " ans2: " << ans2 << endl;
}

This is because the * and % operators have the same precedence, so the latter expression is parsed as:

(((a % M) * b) % M ) % M

so if b > M, there is an increased chance of overflow as we don’t reduce b to less than M before multiplying it by a % M as we do in the former case.

3 Likes
3

THANK YOU SO MUCH DID’NT KNEW THIS BEFORE

1 Like