Modular Exponentiation

Modular Exponentiation

Codeforces easy

Given two number \(n\) and \(m\) print \(m \bmod 2 ^ n\)

Note

For two numbers x and y where y > x, the modulo satisfies x % y == x.

Solution

Directly computing \(2^n\) can lead to integer overflow. To avoid this, we can use a variable power initialized to 1 and iteratively multiply it by 2 in a loop that runs \(n\) times.

During each iteration, if power exceeds m, we can immediately conclude that the result should be m. If the loop completes without power exceeding \(m\), we know no overflow occurred, and the result can be safely computed as power % m.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int power = 1;

    for (int i = 0; i < n; i++) {
        power *= 2;

        if (power > m) {
            cout << m << endl;
            break;
        }
    }

    if (power <= m) {
        cout << m % power << endl;
    }
}