_bzoj2005 [Noi2010]能量采集
2024-08-30 06:31:58
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2005
令F(i)表示i | gcd(x, y)的对数，f(i)表示gcd(x, y) = i的对数，那么显然
f(i) = F(i) - f(2 * i) - f(3 * i) - ...
F(i)很好求，显然，F(i) = (n / i) * (m / i)，除法向下取整。
之后就简单了~
#include <cstdio>
#include <algorithm> const int maxn = 100005; int n, m, lmt;
long long f[maxn], ans; int main(void) {
scanf("%d%d", &n, &m);
lmt = std::min(n, m);
for (int i = lmt; i; --i) {
f[i] = (long long)(n / i) * (long long)(m / i);
for (int j = i << 1; j <= lmt; j += i) {
f[i] -= f[j];
}
ans += f[i] * ((i << 1) - 1);
}
printf("%lld\n", ans);
return 0;
}
最新文章
- dotnet core 出现Can not find runtime target for framework '.NETCoreApp,Version=v1.6' 的解决办法
- [z]START WITH CONNECT BY PRIOR子句实现递归查询
- 使用idea开发Springmvc
- 解决jsp中文乱码问题
- 用 Navicat 写mysql的游标
- python在不同层级目录import模块的方法
- delphi 18 屏蔽和替换 右键菜单
- 【转】GitHub平台最火Android开源项目整理——2013-08-25 17
- spring Aop 注解
- 织梦DEDECMS {dede:field name='position'/}标签增加其它属性的
- Implement Hash Map Using Primitive Types
- 06-OC分类、协议、ARC
- 快速构建Windows 8风格应用6-GridView数据控件
- [转]android4.0.3 修改启动动画和开机声音
- 201521123020 《Java程序设计》第7周学习总结
- TDD：什么是桩（stub）和模拟（mock）？
- cf666E. Forensic Examination(广义后缀自动机 线段树合并)
- C# Queue 和Stack的实现
- edraw的符号制作
- cocos2d-x C++ 原始工程引擎运行机制解析