【题解】Codeforces Round 818 (Div.2)

Codeforces Round #818 (Div. 2) A-E题解，即CF1717A-CF1717E，主要是思维，E是数学，这场前五道题的代码是真的简洁。。。。

CF1717A Madoka and Strange Thoughts

题目链接

题意

$t$ 组数据。给定正整数 $n\in[1,10^8]$ ，输出符合条件的整数对 $(a,b)$ 的个数，要求 $1\leq a,b \leq n,\text{lcm}(a,b)\leq 3\gcd(a,b)$

分析

歪解：找规律

将 $\text{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$ 代入条件改成 $3\gcd(a,b)^2\geq ab$ ，打表：

void solve()
{
    int n = 100;
    for (int i = 1, cnt = 0; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            if (3 * __gcd(i, j) * __gcd(i, j) >= i * j)
                cnt++;
        cout << cnt << '\n';
    }
}

可以看到规律是答案依次加一个数列 ${1,3,3,3,1,5}$ ，设一个数组就行了：

int c[10] = {0, 1, 4, 7, 10, 11, 16};
void solve()
{
    int n;
    cin >> n;
    cout << n / 6 * c[6] + c[n % 6] << '\n';
}

正解

根据数论知识：设$a={\rho_1}^{r_1}{\rho_2}^{r_2}\cdots {\rho_k}^{r_k},b={\rho_1}^{s_1}{\rho_2}^{s_2}\cdots {\rho_k}^{s_k}$，则：

$\gcd(a,b)={\rho_1}^{\min(r_1,s_1)}{\rho_2}^{\min(r_2,s_2)}\cdots {\rho_k}^{\min(r_k,s_k)}\\ \text{lcm}(a,b)={\rho_1}^{\max(r_1,s_1)}{\rho_2}^{\max(r_2,s_2)}\cdots {\rho_k}^{\max(r_k,s_k)}$

所以 $a,b$ 的质因子 $> 3$ 的次数必须相等，质因子 $2,3$ 可以存在一个次数不等，但次数只能差一个，即 $a=2b$ 或 $a=3b$ ，答案是所有的 $(a,a)$ （共 $n$ 个）、所有的二倍关系数对（共 $2\times \lfloor \frac{n}{2}\rfloor$ 个）、所有的三倍关系数对（共 $2\times \lfloor \frac{n}{3}\rfloor$ 个）

代码

void solve()
{
    int n;
    cin>>n;
    cout << n + n / 2 * 2 + n / 3 * 2 << '\n';
}

CF1717B Madoka and Underground Competitions

题目链接

题意

$t$ 组数据，给一个 $n\times n$ 的方格图，其中坐标 $(r,c)$ 的字符是 X ，其余是 . ，要求方格中每连续 $k$ 个格子（横竖方向都满足）中必须要出现至少一个 X，要求给出填X的方案，使得X个数尽可能少

分析

不管已填的字符，发现必须按对角线填：

都是每 $k$ 个填一个X，才能最少的情况下满足要求，那么从给定的 $(r,c)$ 坐标看，每 $k$ 个把这一行填满（溢出回头），每下一行的起始空格 $+1(\mod k)$，上一行起始空格 $-1(\mod k)$ ，看代码更容易理解

代码

bool mp[N][N];
void solve()
{
    int n, k, r, c;
    cin >> n >> k >> r >> c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            mp[i][j] = 0;        // 清零
    int curc = c % k;            // 计算r行的填X起始空格数
    int cur = curc;              // 起始空格数变量，随填的行数修改
    for (int i = r; i <= n; i++) // 往下填
    {
        for (int j = cur; j <= n; j += k)
            if (j)
                mp[i][j] = 1;
        cur = (cur + 1) % k; // 修改起始空格数
    }
    cur = curc;
    for (int i = r - 1; i > 0; i--) // 往上填
    {
        cur = (cur - 1 + k) % k;    
        for (int j = cur; j <= n; j += k)
            if (j)
                mp[i][j] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << (mp[i][j] ? 'X' : '.');
        cout << '\n';
    }
}

CF1717C Madoka and Formal Statement

题目链接

题意

$ t$ 组数据。给定$a_1,a_2,\cdots, a_n$ 和 $b_1,b_2,\cdots, b_n$ ，试图用操作使 $a_i=b_i$ 。将数列首尾相连，如果数列 $a$ 中左边的数不大于右边的数，它可以一直 $+1$ ，输出是否可以完成变换。

分析

显然，因为没有减法操作，只要有一个 $a_i>b_i$ 就一定不可能完成

其他情况，这题我写的时候分析复杂了，实际上定点（$ a_i=b_i$）没出现之前，这个数列中的每个数都可以尽情上升，一旦出现定点，定点会限制其左边的数列最多呈一个递减 $1$ 的序列。因此除非本来 $a_i=b_i$ ，否则 $a_i$ 最多变换成 $b_{i+1}+1$ ，则要求 $b_i\leq b_{i+1}+1$

代码

int a[N], b[N];
void solve()
{
    int n;
    cin >> n;
    bool flag = true;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        if (b[i] < a[i])
            flag = false;
    }
    for (int i = 0; i < n && flag; i++)
        if (b[i] > a[i] && b[i] > b[(i + 1) % n] + 1)
            flag = false;
    if (flag)
        cout << "YES";
    else
        cout << "NO";
    cout << '\n';
}

CF1717D Madoka and The Corruption Scheme

题目链接

题意

给定一场比赛，有 $2^n$ 个参赛者每一轮两两淘汰（树形），我们可以指定每一局左边/右边的参赛者取胜，我们希望获胜的参赛者编号最小。赞助商有 $k $ 次机会可以调整某一局的结果，求不管如何调整能得到的最小的获胜者的编号，$1≤n≤10^5,1≤k≤min(2n−1,10^9)$

分析

总共会进行 $n$ 轮比赛，如果 $k\geq n$ ，赞助商可以让编号最大的连赢 $k$ 轮，答案是 $2^n$ ；否则赞助商能改变 $k$ 次，那么如果一个人输了 $k$ 轮（假设输了一直做修改）后，赞助商也没法改变了，就要找出所有的到赢家的路上会输 $k$ 次以上的人，全部给大编号就行了

每个人走到赢家的路上都有 $n$ 轮比赛，找出输 $[k+1,n] $ 次的节点个数

证明一个结论：按题意这样的 $n$ 层二叉树，输 $i$ 次的节点有 $C(n,i)$ 个（即 $n$ 个中选 $i$ 个的情况数）

假设 $i$ 次成立，下证 $i+1$ 次的节点个数有 $C(n,i+1)$ 个：

对于到达 $i$ 层中的每一条路，连接下面（第 $i+1$ 层的两个节点）的有一条路是赢一条路是输，包含这条路沿伸一个单位后的所有情况，所以成立

第一层的节点连接两个节点，一个赢一个输，是一轮的所有情况，因此原结论成立

所以答案就是 $2^n-\sum_{i=k+1}^{n}C(n,i)$

代码

ll qpow(ll m, ll n)		// 快速幂
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = (ans * m) % mod;
        m = (m * m) % mod;
        n >>= 1;
    }
    return ans;
}
void init(int n)		// 初始化逆元和阶乘，用于计算组合数
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
ll C(int x, int y)		// 组合数计算
{
    if (x < y || y < 0)
        return 0;
    return 1ll * fac[x] * inv[x - y] % mod * inv[y] % mod;
}
void solve()
{
    ll n, k;
    cin >> n >> k;
    init(n);
    ll ans = qpow(2, n);
    for (int i = k + 1; i <= n; i++)
        ans = (ans - C(n, i) + mod) % mod;
    cout << ans << '\n';
}

CF1717E Madoka and The Best University

题目链接

题意

简洁明了，对于 $n\in[3,10^5]$ 求 $\sum_{a+b+c=n}\text{lcm}(c,\gcd(a,b))$

分析

枚举两个数$O(n^2)$ 肯定不行，从式子来说尝试枚举 $a+b=i$ ，则原式$=\text{lcm}(n-i,\gcd(a,b))$ ，需要在不到 $O(n)$ 的复杂度情况下找到 $\gcd(a,b)$ 的所有可能情况和其对应的 $(a,b)$ 个数

设 $\gcd(a,b)=j$ ，则 $a=xj,b=yj,\gcd(x,y)=1,(x+y)j=i$ ，所以如果反过来枚举 $j$ ， $i$ 就只需枚举 $j$ 的倍数，枚举的角度可以把时间复杂度降到 $O(n\log n)$

$\gcd(x,y)=\gcd(x,\frac{i}{j}-x)=1=\gcd(x,\frac{i}{j})$ ，所以 $x$ 的可能取值为 $\frac{i}{j}$ 的所有质因子，共有 $\varphi(\frac{i}{j})$ 个，$(i,j)$ 的情况下获得的结果是 $\text{lcm}(n-i,j)*\varphi(\frac{i}{j})$ 个

将上述所有枚举的情况加起来就可以了，枚举的复杂度已经说过，每次要求一个最小公倍数，复杂度粗略记为 $O(\log n)$ ，线性筛预处理欧拉函数的复杂度为 $O(n)$ ，则算法的总复杂度为 $O(n\log^2 n)$

代码

bool check[N + 10];
int phi[N + 10];
int prime[N + 10];
int tot; //素数的个数
void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
                break;
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j]; // 利用性质
                break;
            }
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1); // 积性函数
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    phi_and_prime_table(n);
    ll ans = 0;
    for (ll j = 1; j <= n; j++)
        for (ll i = j + j; i <= n; i += j)
            ans = (ans + (n - i) * j / __gcd(n - i, j) * phi[i / j] % mod) % mod;
    cout << ans << '\n';
}