题解：CF476C Dreamoon and Sums

· · 题解

CF476C 题目传送门

题目大意

对于给定的两个正整数 a 和 b，设正整数 x 除以 b 的商和余数分别为 d 和 m，如果 1 \leq \frac{d}{m} \leq a，则称 x 为“优美”的整数。现有两个整数 a 和 b，请你计算所有“优美”的整数的总和。结果对 10^9 + 7 取模后输出。

解决思路

逆向思维思考一下，反着来求出所有的 x，即通过遍历所有的 a 和 b 求出所有的 x 但是光是这样，那肯定会超时的。所以我们可以通过提取公因式，这里可以提出 i，利用等差数列求和即可。但是这里要注意数据范围，a^3 的范围大约是 10^21，超过了 long long 的范围。

代码展示

#include <iostream>
//拒绝万能头
#define ll long long
//不开 long long 见祖宗 
using namespace std;

const ll MOD=1e9+7;
ll a,b,ans,sum;

int main()
{
    cin>>a>>b;
    sum=(b*(b-1)/2)%MOD;
    for(int i=1;i<=a;i++)
    {
        ll x=(sum*((i*b+1)%MOD))%MOD;
        ans+=x;
        ans%=MOD;//注意多次取模
    }
    cout<<ans%MOD<<endl;
    return 0;
}