2010-1087

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意是：在三维空间的第一象限每一个整点有一个基站。(1, 1, 1)这个坐标的基站一开始是发送状态，并且发送编号为1的信息，而除此之外的其他基站一开始都处在接收信息状态。当一个基站接受到所有它能解码的信息之后，它就转为发送状态，并且发送它所接收到的最大编号+1的信息。能解码定义为：(x, y, z)能解码(x', y', z')当且仅当x' | x且y' | y且z' | z。现在问从(1, 1, 1)到(x, y, z)的所有节点一共发送多少信息。

设(x, y, z)发送的信息量为f(x, y, z)。则f(x, y, z) = max{f(x', y', z') | x', y', z' 分别是 x, y, z的因子} + 1。假设操作M是把x, y, z中的一个数除以它的一个质因数。则f(x, y, z) ≥ f(M(x, y, z)) + 1 ≥ f(M(M(x, y, z))) + 1 ≥……因此，f(x, y, z) = max{f(x', y', z') | x', y', z' 一共只比 x, y, z少了一个质因子} + 1。因此易得f(x, y, z)就是x, y, z的质因子个数之和。

因此可以先预处理一维的时候的情况，然后三维分开计算即可。

{{{
#!cpp
#include <cstdio>
#include <cstring>

typedef long long LL;

int x, y, z;
int num;
int minp[500005], p[500005];
LL cnt[500005];

void prime() {
    int n = 500000;
    num = 0;
    memset(minp, 0, sizeof(minp));
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            minp[i] = i;
            p[num++] = i;
        }
        for (int j = 0; j < num && i * p[j] <= n; j++) {
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}

void init() {
    cnt[0] = 0;
    for (int i = 1; i <= 500000; i++) {
        cnt[i] = cnt[i - 1];
        for (int t = i; t != 1; t /= minp[t]) {
            cnt[i]++;
        }
    }
}

int main() {
    prime();
    init();
    while (scanf("%d%d%d", &x, &y, &z) != EOF) {
        LL res = cnt[x] * y * z + cnt[y] * x * z + cnt[z] * x * y + (LL)x * y * z;
        printf("%lld\n", res);
    }
    return 0;
}
}}}

题目大意是：在三维空间的第一象限每一个整点有一个基站。(1, 1, 1)这个坐标的基站一开始是发送状态，并且发送编号为1的信息，而除此之外的其他基站一开始都处在接收信息状态。当一个基站接受到所有它能解码的信息之后，它就转为发送状态，并且发送它所接收到的最大编号+1的信息。能解码定义为：(x, y, z)能解码(x', y', z')当且仅当x' | x且y' | y且z' | z。现在问从(1, 1, 1)到(x, y, z)的所有节点一共发送多少信息。

设(x, y, z)发送的信息量为f(x, y, z)。则f(x, y, z) = max{f(x', y', z') | x', y', z' 分别是 x, y, z的因子} + 1。假设操作M是把x, y, z中的一个数除以它的一个质因数。则f(x, y, z) ≥ f(M(x, y, z)) + 1 ≥ f(M(M(x, y, z))) + 1 ≥……因此，f(x, y, z) = max{f(x', y', z') | x', y', z' 一共只比 x, y, z少了一个质因子} + 1。因此易得f(x, y, z)就是x, y, z的质因子个数之和。

因此可以先预处理一维的时候的情况，然后三维分开计算即可。

#include <cstdio>
#include <cstring>
typedef long long LL;
int x, y, z;
int num;
int minp[500005], p[500005];
LL cnt[500005];
void prime() {
    int n = 500000;
    num = 0;
    memset(minp, 0, sizeof(minp));
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            minp[i] = i;
            p[num++] = i;
        }
        for (int j = 0; j < num && i * p[j] <= n; j++) {
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}
void init() {
    cnt[0] = 0;
    for (int i = 1; i <= 500000; i++) {
        cnt[i] = cnt[i - 1];
        for (int t = i; t != 1; t /= minp[t]) {
            cnt[i]++;
        }
    }
}
int main() {
    prime();
    init();
    while (scanf("%d%d%d", &x, &y, &z) != EOF) {
        LL res = cnt[x] * y * z + cnt[y] * x * z + cnt[z] * x * y + (LL)x * y * z;
        printf("%lld\n", res);
    }
    return 0;
}