比赛 |
2022级数学专题练习赛9 |
评测结果 |
AAAAAAAAAA |
题目名称 |
能量采集 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2023-02-08 18:47:04 |
显示代码纯文本
// Problem: P1447 [NOI2010] 能量采集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1447
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e5;
int n,m,prime[N + 5],cnt;
bool flag[N + 5];
i64 phi[N + 5];
int main() {
freopen("energy2010.in","r",stdin);
freopen("energy2010.out","w",stdout);
scanf("%d %d",&n,&m);
i64 ans = -1ll * n * m;
if(n > m)
std::swap(n , m);
for(int i = 2;i <= n;++ i) {
if(!flag[i])
prime[++ cnt] = i,phi[i] = i - 1;
for(int j = 1;j <= cnt&&i * prime[j] <= n;++ j) {
flag[i * prime[j]] = true;
if(i % prime[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else
phi[i * prime[j]] = phi[i] * prime[j];
}
}
phi[1] = 1;
for(int i = 1;i <= n;++ i)
phi[i] += phi[i - 1];
for(int l = 1,r;l <= n;l = r + 1) {
r = std::min(n / (n / l) , m / (m / l));
ans += 2ll * (phi[r] - phi[l - 1]) * (n / l) * (m / l);
}
printf("%lld",ans);
return 0;
}