### ZOJ Monthly, November 2010解题报告 » ZOJ3435

ZOJ3435.cpp

```#include <cmath>
#include <cstdio>
#include <numeric>
#include <algorithm>

using namespace std;

const int MAXN = 1000001;

int p[MAXN];

void init() {
p[1] = 1;
for(int i = 2; i < MAXN; ++i) {
if (!p[i]) {
for (int j = i; j < MAXN; j += i) {
p[j] = i;
}
}
}
for (int i = 2; i < MAXN; ++i) {
p[i] = (i / p[i] % p[i] == 0 ? 0 : -p[i / p[i]]);
}
partial_sum(p, p + MAXN, p);
}

long long gao(long long x, long long y) {
if (x > y) {
return gao(y, x);
}

long long ret = 0;
for (long long i = x, j; i > 0; i = j) {
long long xx = x / i, yy = y / i;
j = max(x / (xx + 1), y / (yy + 1));
ret += xx * yy * (p[i] - p[j]);
}
return ret;
}

long long gao(long long x, long long y, long long z) {
if (x > y) {
return gao(y, x, z);
}
if (x > z) {
return gao(z, y, x);
}

long long ret = 0;
for (long long i = x, j; i > 0; i = j) {
long long xx = x / i, yy = y / i, zz = z / i;
j = max(max(x / (xx + 1), y / (yy + 1)), z / (zz + 1));
ret += xx * yy * zz * (p[i] - p[j]);
}
return ret;
}

int main() {
long long x, y, z;
long long ans;

init();
while (scanf("%lld%lld%lld", &x, &y, &z) != EOF) {
--x;
--y;
--z;
ans = 3;
ans += gao(x, y);
ans += gao(y, z);
ans += gao(z, x);
ans += gao(x, y, z);
printf("%lld\n", ans);
}

return 0;
}

// Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
// 375 	2010-11-10 00:22:04 	Accepted 	I 	C++ 	260 	4084 	watashi@Zodiac 	Source
```