2020年牛客暑期多校训练营（第七场）

D - Fake news

题意：输入一个数num，然后从1到num，将每个数的平方相加，判断得到的数是否为平方数。

实际上只有1与24满足题意

下面是没有发现只有1，24满足题意，暴力求解的代码

#include <cstdio>
#include <cmath>

typedef long long LL;
const double eps = 1e-8;

int main()
{
    int n;
    scanf("%d", &n);

    while (n--) {
        LL num;
        LL sum = 0;
        scanf("%lld", &num);

        for (LL i = num; i > 0; i--)
            sum += i * i;

        if ((double)sqrt((double)sum) - (LL)sqrt((double)sum) < eps)
            printf("Fake news!\n");

        else
            printf("Nobody knows it better than me!\n");
    }

    return 0;
}

显然会爆掉，这里可以使用平方和公式 $1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ 计算最终结果，但是还是会爆掉，需要对表达式中 $n(n + 1)(2n + 1)$ 两两除以gcd，然后对sum开根，观察结果是否为整数来判断sum是否为平方数；还可以sum == (int)sqrt(sum) * (int)sqrt(sum)判断sum是否为平方数

下面是AC的代码：

#include <cstdio>

typedef long long LL;

int main()
{
    int n;
    scanf("%d", &n);

    while (n--) {
        LL num;
        scanf("%lld", &num);

        if (num == 1 || num == 24)
            printf("Fake news!\n");

        else
            printf("Nobody knows it better than me!\n");
    }
    return 0;
}

H - Dividing

题意：定义了一种元组-Legend Tuple。输入N，K，当1 <= n <= N; 1 <= k <= K时，

(1, k)始终是Legend Tuple
(n, k)是Legend Tuple时，(n + k, k)也是Legend Tuple
(n, k)是Legend Tuple时，(nk, k)也是Legend Tuple

所以当输入N，K后，计算有多少个Legend Tuple，由于数量可能会多，所以结果以 $10^9 + 7$ 的模为结果

思路：判断当前(n, k)；从(1, k)到当前的(n, k)，如果经历了第三种变换，那么当前的n一定是k的倍数；如果没有经历过第三种变换，n = xk + 1(x为整数)，(n - 1)一定是k的倍数

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const double epse = 1e-5;
const int mod = 1e9 + 7;

int main()
{
    LL n, k;
    scanf("%lld%lld", &n, &k);
    LL cut = 0, ans = 0;

    //n是k的倍数
    for (int i = 2; i <= k; i = cut + 1) {
        if (i > n)
            break;

        cut = min(n / (n / i), k);
        ans = (ans + (cut - i + 1) * (n / i)) % mod;
    }

    //n-1是k的倍数
    for (int i = 2; i <= k; i = cut + 1) {
        LL ano_n = n - 1;
        if (i > ano_n)
            break;

        cut = min((ano_n) / (ano_n / i), k);
        ans = (ans + (cut - i + 1) * (ano_n / i)) % mod;
    }

    ans = (ans + k - 1) % mod;
    ans = (ans + n) % mod;

    printf("%lld\n", ans);
    return 0;
}

B - Mask Allocation

题意：输入 $n \times m$ 个口罩，然后将他们分组，分成的组数尽量最少。这些组中的一些组可以组合起来放在一个盒子里，盒子里可以有一个组，也可以有多个组。1.如果得到n个盒子，那么不论盒子里有多少组，但每个盒子里一定都是m个口罩；2.如果得到m个盒子，同样不论盒子里有多少组，每个盒子里一定都是n个口罩

思路：假设n < m(否则交换n，m)，那么先得到n组，每组里有n个口罩；剩下的口罩有(m - n)n个，使用递归，也就是先判断(m - n)与n的大小关系，继续分组。递归结束的条件：口罩分完， $n \times m = 0$
当需要分给n座医院时将剩余的组和之前的n组合放在一个盒子里，当需要分给m座医院时之前的n组不变，将剩余的组放在(m-n)个盒子里

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> ans;

//递归，结束条件为口罩分完，较小的数为零
void dfs(int n, int m) {
    if (m == 0)
        return ;

    for (int i = 0; i < (n / m) * m; i++)
        ans.push_back(m);

    dfs(max((n % m), m), min((n % m), m));
}

int main()
{
    int t;
    scanf("%d", &t);

    while(t--) {
        ans.clear();
        int n;
        int m;
        scanf("%d%d", &n, &m);

        if (n < m)
            swap(n, m);

        dfs (n, m);
        //最小组数
        printf("%d\n", ans.size());

        for(int i = 0; i < ans.size(); i++)
            printf("%d ", ans[i]);

    }
    printf("\n");
    return 0;
}