Ý tưởng

Xét tổng: `A = 1*2^0 + 2*2^1 + 3*2^2 + ... + n*2^(n-1)`

`=2^0 + 2^1 + 2^1 + 2^2 + 2^2 + 2^2 + ... + underbrace{2^(n-1)+...+2^(n-1)}_{n \ "hạng tử"}`

`=(2^0 + 2^1 + ... + 2^(n-1)) + (2^1 + ... + 2^(n-1)) + ... + (2^(n-2) + 2^(n-1)) + 2^(n-1)`

`=underbrace{(2^n - 2^0) + (2^n - 2^1) + ... + (2^n - 2^(n-2))}_{n-1 \ "hạng tử"} + 2^(n-1)`

`=(n-1)*2^n - (2^0 + 2^1 + ... + 2^(n-2))+2^(n-1)`

`=(n-1)*2^n - (2^(n-1) - 1)+2^(n-1)`

`=(n-1)*2^n + 1`

`=>` `S = A % k = ((((n-1) % k)*(2^n % k)) % k + (1 % k)) % k`

`=>` Yêu cầu bài toán tương đương với tính `2^n % k`

Bạn có thể tham khảo trên mạng về modulo Ấn Độ để tính `2^n % k` với độ phức tạp `O(log_2(n)^2)`

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll m_multiply(ll a, ll b, ll m) {
    if (b == 0) return 0;
    
    ll t = m_multiply(a, b / 2, m) % m;
    
    if (b & 1) return ((t + t) % m + a % m) % m;
    else return (t + t) % m;
}

ll m_power(ll a, ll b, ll m) {
    if (b == 0) return 1LL;
    
    ll half = m_power(a, b / 2LL, m) % m;
    half = m_multiply(half, half, m);
    
    if (b & 1) return m_multiply(half, a, m);
    else return half;
}

int main() {
    ll n, k;
    while (cin >> n) {
        cin >> k;
        cout << (((((n - 1) % k)*m_power(2, n, k)) % k) + (1 % k)) % k << endl;
    }
    return 0;
}