Modular Exponentiation

Modular Exponentiation

Codeforces easy

لديك رقمان \(n\) و \(m\)، اطبع \(m \bmod 2 ^ n\).

Noteملحوظة

بالنسبة لرقمين x و y حيث y > x، فإن x % y == x.

Solution

يمكن أن تؤدي عملية حساب \(2^n\) مباشرة إلى تجاوز حدود النوع int . لتجنب ذلك، نستخدم متغيرًا power مهيأً بقيمة مبدئية تساوي 1 ونضربه في 2 بشكل متكرر في حلقة تتكرر \(n\) مرة.

أثناء كل تكرار، إذا أصبح power أكبر من m، يمكننا على الفور استنتاج أن الناتج يجب أن يكون m. إذا اكتملت الحلقة دون أن يتجاوز power قيمة m، يمكننا استنتاج أن لا تجاوز حصل لحدود النوع int ، ويمكن حساب الناتج كـ m % power.

#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;
    }
}