题解 | 商店

#include<bits/stdc++.h>

#define ll unsigned long long
#define all(A) A.begin(),A.end()
#define QwQ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using namespace std;

ll MOD = 1e9 + 7;

ll ercf(ll x) {
    ll ans = 1, er = 2;
    while(x) {
        if(x & 1) {
            ans = ans * er % MOD;
        }
        x >>= 1;
        er *= er;
        er %= MOD;
    }
    return ans;
}

void go() {
    ll n, m; cin >> n >> m;
    ll ans;

    if (n >= m) {
        ans = (2 * m) % MOD;
    } else {
        ll r = m % n;
        ll b = m / n;
        ll te1 = r * ercf(b + 1) % MOD;
        ll te2 = (n - r) * ercf(b) % MOD;
        ans = te1 + te2;
    }
    ans %= MOD;

    cout << ans << '\n';
}

int main() {
    QwQ
    int t; t = 1;
    cin >> t;
    while(t--) {
        go();
    }
}

当成笔记来写。

这题用到了快速幂，将次方数看成二进制数来累乘。例如 2^5 = 2^101(二进制) = 2^(4*1) * 2^(2*0) * 2^(1*1).里面2^1,2^2,2^4是逐渐平方递增的，括号里的1, 0, 1就是二进制的1和0，代码中的er就是逐渐增加的数，从二进制的右边向左边遇1就乘。