比赛 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;
}