专栏文章

题解：CF476C Dreamoon and Sums

RRex01
CF476C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqag1u4
此快照首次捕获于
2025/12/04 01:35
3 个月前
此快照最后确认于
2025/12/04 01:35
3 个月前
查看原文

CF476C 题目传送门

题目大意

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

解决思路

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

代码展示

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...