Modular Exponentiation

Modular Exponentiation

Codeforces easy

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

ملاحظةملحوظة

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

الحل

يمكن أن تؤدي عملية حساب \(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;
    }
}