题解 | 商店

#include <iostream>
using namespace std;
const int MOD =1000000007;
long long price(long long base,long long exp)
{
    long long a=1;
    while(exp!=0) 
    {
        if(exp%2==1) a=(a*base)%MOD;
        base=(base*base)%MOD;
        exp/=2;
    }
    return a;
}//快速幂算法可将算法的时间复杂度降低为O（lgn）
void solve()
{
    long long n,m,ans=0;
    cin>>n>>m;
    if(n>=m)
    {
        ans=(m*2)%MOD;
    }
    else 
    {
        long long p=m/n;//所必须的最小重量是多少
        long long q=m%n;//余数代表所需要的比最小重量重1的个数
        ans=(price(2,p)*(n-q)+price(2,p+1)*q)%MOD;
    }
    cout<<ans<<endl;
}
int main() 
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

这道题有2点非常重要

1.使用快速幂算法降低时间复杂度

2.最低价格的计算（把题目给的例子列举观察即可发现规律，我给到的算法就没有使用贪心策略而是数学规律）