BZOJ2005 [NOI2010 能量采集]

传送门

题目大意

求:
$$
2\sum_{i=1}^n\sum_{j=1}^m(i,j)-nm\
n,m\le10^5
$$

解析

这个数据范围很小,直接枚举$gcd$即可。

再大一点可以莫比乌斯反演(咕咕咕)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define DREP(i, s, e) for(int i = s; i >= e ;i--)
#define REP(i, s, e) for(int i = s; i <= e ;i++)

#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>
#define int long long

using namespace std;
const int maxn = 1e5 + 10;

int n, m, ans, cnt[maxn];
//ans = \sum_i \sum_j (i,j) - nm

signed main()
{
#ifdef CraZYali
freopen("2005.in", "r", stdin);
freopen("2005.out", "w", stdout);
#endif
cin >> n >> m;
ans = -n * m;
int N(min(n, m));
DREP(i, N, 1)
{
int &c = cnt[i];
c = (n/i) * (m/i);
for (int j = i + i; j <= N;j += i) c -= cnt[j];
ans += i * c * 2;
}
cout << ans << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×