数学——A. K-divisible Sum + D. Exam in MAC

A. K-divisible Sum

题目：

思路：

以下 “[xxx]” 符号均代表向上取整

我们假设总和是sum，那么就有sum = k * cnt

要想最大值最小，肯定是要让sum尽可能小，这样每个元素都能变小

最小情况是 sum 恰好等于 n 时，此时有 n <= k * cnt

则 cnt 满足 cnt >= [n / k]，当其取最小值时，sum有最小

此时既然我们知道sum的最小值了，那我们来探讨一下数组中最大值的最小值应该是多少

显然最小值应该是 [sum / n]，所以我们便可写出代码了

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve()
{
    int n, k;
    cin >> n >> k;
    int cf = (k + n - 1)/ k;
    cout << (cf * k + n - 1) / n << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D. Exam in MAC

题目：

思路：

这题让我们选出满足题意的（x,y）数对，首先看数据，居然高达1e9，那么显然不能直接暴力枚举

这题要以反向的思路来求，因为满足的很多，但是不满足的很少

那我们先什么都不考虑，我们的数对有多少种选择呢？（无重复）

显然是 (c+1 +1) * (c+1) / 2 种，为什么？

当 x 选 0 时，y 可以选 c + 1种，当 x 选 1 时，y 可以选 c 种，以此类推，最后发现这是一个等差数列，那么直接求和就是以上公式了

接下来我们考虑不符合的

首先考虑 x + y ∈ s

也就是对于任意的 s[i]，要使得 x + y = s[i]，一共有多少种选择？

其实和上述一样的思路，这里的答案是 s[i] / 2 + 1 种（因为还有0）

接下来考虑 y - x ∈ s

对于 y - x = s[i]，也就是 y = s[i] + x，可以看出 y 的取值范围是 s[i] <= y <= c，那么显然，对于范围内任选一个数，都有唯一确定的 x 与其对应，所以这里的答案是 c - s[i] + 1

那么到这就结束了吗？显然没有，因为还有可能这些情况中还有两种情况都符合的情况

那么根据容斥原理，我们只需要求出两种情况都符合的情况，然后减去即可

那么我们来看看如何计算呢，首先有以下式子

x + y = s[i] 且 y - x = s[j]，其中 s[i] 可以等于 s[j]，那么显然对于这个二元一次方程，我们可以解出对于 s[i] 和 s[j] 这种情况的唯一解，但是要注意，s[i] 与 s[j] 的奇偶性一定要相同，否则解不是整数，所以我们只需要统计 s 中的奇数和偶数就行了，那接下来算一下他们的奉献

对于任意奇偶，其奉献是 even/odd * (even/odd + 1) / 2，这其实和上面一样，自己草稿纸上也能写出来

至此题目分析完毕，还是比较简单的，将复杂变简单

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<int> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    int ans = 1LL * (c + 1) * (c + 2) / 2LL;
    int even = 0, odd = 0;
    for (int i = 0; i < n; i++)
    {
        ans -= s[i] / 2LL + 1;
        ans -= c - s[i] + 1LL;
        if (s[i] % 2)
            odd++;
        else
            even++;
    }
    ans += 1LL * even * (even + 1) / 2LL;
    ans += 1LL * odd * (odd + 1) / 2LL;
    cout << ans << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}