luogu1447 能量采集
2024-08-31 05:56:25
题目大意
给出m,n,对于每一个整数x∈[1,m],y∈[1,n]都有一点(x,y)。处理每个点所需要的能量为2*k+1,k为该点到原点经过的点的数量(不包括该点本身)。求处理所有点所需要的能量和。
思路
先考虑考虑暴力,即枚举每一个点,求其所需的能量。我们怎么知道一个点(x,y)的k值呢?
性质1:k=gcd(x,y)-1
既然是直线,所以我们可以想到斜率。我们规定斜率用两个互质的整数:分子和分母来表示。现在我们要求k。小学时我们是怎么化简分数的?分子分母分别除以它们的最大公因数即可。意思就是说,上述所说的分子是y/gcd(x,y),分母是x/gcd(x,y)。因为x=gcd(x, y) * (x / gcd(x, y)), y也是如此,所以对于每个整数a∈1~gcd(x,y),点(a*(x/gcd(x,y)), a*(y/gcd(x,y)))都是在原点与点(x,y)直线上的整点。抠掉当前点,因此,k=gcd(x,y)-1。
对于每个点都来一次gcd很慢,但是我们知道,一个约数i在1~n范围内是n/i个数的约数。gcd也是个约数,如果能利用到这一点,不就可以同时处理很多个点了吗?
现在我们的思路是:既然只要gcd(x,y)都相同,该点所需要的能量就相同,所以我们看看最大公约数等于i的数对(x,y)个数f[i]是多少,再让f[i]*(2*i-1)就是这个最大公因数对答案ans做出的贡献。
性质2:f[i]=公约数中含有i的个数-sum foreach j(i<j<=min(m,n)/i) (f[i*j])
容斥原理,如果i*j是某个数对的最大公因数,则i就不是它的最大公因数。把这样的点都抠掉,剩下的就都是关于最大公因数是i的了。
性质3:公约数含有i的个数=m/i*n/i
数对(x,y)的公约数中含有i当且仅当i既是x的约数又是y的约数。先选择约数中含有i的x,其有m/i个。这时再选择y,其有n/i个。根据乘法原理,因为是依次选择,所以两个式子相乘。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define ll long long
const int MAX_N = 1000010; int main()
{
ll n, m, ans = 0;
static ll f[MAX_N];
scanf("%lld%lld", &n, &m);
if (n > m)
swap(n, m);
memset(f, 0, sizeof(f));
for (ll i = n; i >= 1; i--)
{
f[i] = (n / i)*(m / i);
for (ll j = 2; j <= n / i; j++)
f[i] -= f[i*j];
ans += f[i] * (i * 2 - 1);
}
printf("%lld\n", ans);
return 0;
}
最新文章
- jquery替换所有逗号
- Node.js 学习资源
- 3D数学 ---- 矩阵和线性变换[转载]
- hibernate 不识别union解决方法
- mysql之对视图的操作
- BZOJ 2351 Matrix(哈希)
- HDU 2023题解分析
- Access SQL实现连续及不连续Rank排名
- JS立即执行函数表达式(IIFE)
- 201521123009 《Java程序设计》第9周学习总结
- anaconda安装第三方库
- springboot集成swagger
- C#:StreamReader读取.CSV文件(转换成DataTable)
- BZOJ 2957: 楼房重建 [线段树 信息合并]
- 数据库原理 - 序列7 - Binlog与主从复制
- 【shell实例】定时21:00-21:05,循环调用DSQL脚本,其它时段自动退出
- Java中的String,StringBuilder,StringBuffer
- form中的button默认提交事件
- 一目了然了解JAVA集合体系
- HBase最佳实践-管好你的操作系统
热门文章
- Linux安装java jdk、mysql、tomcat
- 基于mybatis向oracle中插入数据的性能对比
- Sql语句优化-查询两表不同行NOT IN、NOT EXISTS、连接查询Left Join
- mssql server 2005自动备份数据库
- phpmyadmin搭建
- AI:IPPR的模式生成-学习/训练方式(基本结构)
- 三维重建面试4:Jacobian矩阵和Hessian矩阵
- Android使用NDK---函数参数传递-基本类型和数组
- 【sqli-labs】 less29 GET- Error based -Impidence mismatch -Having a WAF in front of web application (GET型基于错误的带有WAF注入)
- (转)C#开发微信门户及应用(5)--用户分组信息管理