题目大意
有一个N*M的网格,坐标为(1,1)/(1,2)….(N*M)
每个格点会向(0,0)用光束传输能量,光束上每出现一个格点,就会损失一点能量。
问总共损失的能量数量。
解题报告
老样子,博客附赠样例!
Input:
667 998
Output:
4957744
可以发现一个性质,那就是(x,y)的贡献为gcd(x,y) 原因:
x和y可以每次减去x/gcd(x,y)和y/gcd(x,y)来得到一个可以阻塞(x,y)的点并且此时(x/gcd(x,y),y/gcd(x,y))仍然是整数点
此时应为除数gcd(x,y)为最大的可能除数,所以每次减去的数字是最小化的,所以不存在更多的点能阻塞(x,y)
然而暴力枚举x,y然后gcd的话会T
还用你说!
因为gcd(x,y) < min(n, m),换个角度考虑gcd(x,y)每个数值的出现次数。
设f(i)为最大公因子为i的数对对数
那么i从大往小处理,有以下递推式:
$$ f(i) = \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor – \sum_{j=2}^{ij \leq u} f(i\times j) |u=\max\{n, m\} $$
这显然成立。
复杂度是O(nlogn)的,证明嘛…就是调和级数。
下面给喂代码!
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long LL;
int f[110000];
int main () {
int n, m, u;
scanf("%d%d", &n, &m);
u = std :: max(n, m);
for(int i = u; i; i--) {
f[i] = (n/i)*(m/i);
for(int j = 2; i*j<=u; j++)
f[i] -= f[i*j];
}
LL ans = (LL)n*(LL)m;
for(int i = 2; i<=u; i++)
ans += (LL)2*(i-1)*(LL)f[i];
std :: cout << ans;
}
Join the discussion