E. 别人家的孩子

本题考查程序设计基础。

对于所有 ，求出 、、……、 的最大值，输出即可。

#include <iostream>

using namespace std;

const int N = 100;

int a[N][N], b[N];

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] > b[j])
                b[j] = a[i][j];
    cout << b[0];
    for (int j = 1; j < m; ++j)
        cout << ' ' << b[j];
    cout << '\n';
}

F. 年龄

我们把上述条件转化一下。本题实际上要求我们计算，有多少个整数四元组 满足 ， 能被 整除， 能被 整除，，且 。也就是说，要在 以内选出两个不同的倍数对，其两个元素对应差值相等，求选法的个数。

为了解决这个问题，我们先计算出在 以内所有满足 能被 整除的整数对 。根据调和数列求和的积分估计，这样的整数对有 个。

然后，创建一个数组 ，其中 表示上述整数对中，满足 的整数对 的个数。对于上面计算出的每个整数对 ，都记录 与 的差值 ，令 增加 。这一步的目的是按元素之差给倍数对分组。

于是问题转化为：在同一组内选出两个不同的元素，求选法个数。

因为 的范围是 到 （含边界），所以根据组合计数原理，答案即为

时间复杂度 ，空间复杂度 。

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    LL m = 0, result = 0;
    cin >> m;
    vector<LL> d(m);
    for (LL b = 1; b <= m; ++b)
        for (LL p = 1; p <= m / b; ++p)
        {
            LL a = 0;
            a = b * p;
            ++d[a - b];
        }
    for (LL i = 0; i < m; ++i)
        result += d[i] * (d[i] - 1) / 2;
    cout << result << '\n';
}