Codeforces Round 716 Div.2

已经连着两场掉分了，麻了麻了……

这场开的比较早，在寝室里打的，九点多的时候还比较闹，有点难静下心来思考。加之前一晚喝了酒，感觉脑子里一片混沌——这大概是发挥不好的一点场外原因，还是希望下一场能上大分。

近期还有一个问题是出题出的比较慢，以往我前两题出的都是非常快的，但最近越来越慢，可能要到四五十分钟才能出完，浩元学长这时候C都已经出思路了……

A - Perfectly Imperfect Array

题目大意就是给定一个数组，问能不能从中取出一个子序列，使得其中所有数的乘积为一个完全平方数。如果可以输出NO，不可以输出YES。

对于任意个完全平方数的乘积$a^2b^2\cdotsc^2 = (ab*\cdots *c)^2$，也一定是完全平方数。所以只要有数组中有非完全平方数，那么取该数为子序列就为YES，否则数组中元素全为完全平方数，任意个组合结果仍是完全平方数，为NO。

#include <bits/stdc++.h>

using namespace std;

int T, n;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n;
        v.resize(n);
        for (int &it:v) cin >> it;
        bool flag = true;
        for (int it:v) {
            if (it == 1) continue;
            int tmp = sqrt(it);
            if (tmp * tmp != it) {
                flag = false;
                break;
            }
        }
        if (!flag) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

B - AND 0, Sum Big

一开始读掉了这一条件：

• the sum of its elements is as large as possible.
• 所有元素的和尽可能大。

事实上这条就是解题的关键。首先要满足所有数按位与结果为$0$，其实就是要所有数的同位数字中至少出现一个$0$。我们又知道，即使是二进制下我们也可以仿照十进制进行竖式运算，所以要同时让按位与结果为$0$，还要所有元素的和尽可能大，一定是在所有数的同位数字中有且仅出现一个$0$，这样得到的元素和为$(n-1)*(2^k-1)$。

那很容易就能得知本题的答案，即每位共$n$个数字，从中选一个作为$0$，其它的作为$1$，总共选$k$位，根据乘法原理答案就是$n^k$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

int T;
ll n, k;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n >> k;
        ll ans = 1;
        for (int i = 1; i <= k; i++)
            ans = (ans * n) % MOD;
        cout << ans << endl;
    }
    return 0;
}

C - Product 1 Modulo N

写这题时，我先用下面代码打了个表：

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    for (n = 1; n <= 20; n++) {
        vector<int> ans;
        for (int i = 0; i < (1 << (n - 1)); i++) {
            int tmp = i;
            int cnt = 1, mul = 1;
            vector<int> v;
            while (tmp) {
                if (tmp & 1) {
                    mul *= cnt;
                    v.push_back(cnt);
                }
                cnt++;
                tmp >>= 1;
            }
            if (mul % n == 1 && v.size() > ans.size()) ans = v;
        }
        cout << "n = " << n << ": \n";
        cout << ans.size() << endl;
        for (int it:ans) cout << it << ' ';
        cout << endl;
    }
    return 0;
}

观察了一下$1\leq n\leq 20$下的结果：

n = 1: 
0

n = 2: 
1
1 
n = 3: 
1
1 
n = 4: 
1
1 
n = 5: 
3
1 2 3 
n = 6: 
1
1 
n = 7: 
5
1 2 3 4 5 
n = 8: 
4
1 3 5 7 
n = 9: 
5
1 2 4 5 7 
n = 10: 
3
1 3 7 
n = 11: 
9
1 2 3 4 5 6 7 8 9 
n = 12: 
4
1 5 7 11 
n = 13: 
11
1 2 3 4 5 6 7 8 9 10 11 
n = 14: 
5
1 3 5 9 11 
n = 15: 
8
1 2 4 7 8 11 13 14 
n = 16: 
8
1 3 5 7 9 11 13 15 
n = 17: 
15
1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 
n = 18: 
5
1 5 7 11 13 
n = 19: 
16
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 
n = 20: 
8
1 3 7 9 11 13 17 19 

然后开始找规律，发现首先$n$为偶数时，答案中只有奇数。其次，$n$为奇数时，答案都是从$1\sim n-1$删去几个数构成的。

当天有点迷糊，觉得肯定有进一步的规律，但没想出来是什么，就去求助了下学长。发现学长很早之前就已经给了个思路（那时我甚至不知道他说的是C题）——去掉所有与$n$不互素的数，然后特判$n=4k+2$的情况，这种时候要额外去掉$n-1$。我按这个标准核验了下表，发现似乎确实如此，于是码了下面的代码：

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> prime, ans;

bool check(int k) {
    int len = sqrt(k);
    for (int i = 2; i <= len; i++)
        if (k % i == 0) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    if (n < 5) return cout << "1\n1\n", 0;
    if (check(n)) {
        cout << n - 2 << endl;
        for (int i = 1; i < n - 2; i++)
            cout << i << ' ';
        cout << n - 2 << endl;
        return 0;
    }
    int tmp = n;
    while (tmp > 1) {
        for (int i = 2; i <= n; i++)
            if (tmp % i == 0) {
                tmp /= i;
                prime.emplace_back(i);
                break;
            }
    }
    for (int i = 1; i < n; i++) {
        bool flag = true;
        for (int it:prime) {
            if (i % it == 0) {
                flag = false;
                break;
            }
        }
        if (flag) ans.emplace_back(i);
    }
    if ((n - 2) % 4 == 0 && ans.back() == n - 1) ans.pop_back();
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size() - 1; i++) cout << ans[i] << ' ';
    cout << ans.back() << endl;
    return 0;
}

最后几秒钟没提交上去，当时还小伤心了会儿。结果最后等System Test结束后补交一发WA了，说明上面的贪心处理策略还是有问题的。

不过研究互素的方向是正确的。

首先我们假定选定的序列包含$a$，且其它数乘积为$x$（模$n$），那么有$x$是$a$的逆元，$a$就满足$\gcd(a,n)=1$，否则不能入选。

我们把所有该选的$a$边累乘边取模，可以得到一个小于$n$的数$mul$，$mul$肯定与$n$互质，所以$mul$一定是在前面取过的，如果$mul\neq 1$，就不取这个数。

我不太擅长数论题，只能一知半解借助Tutorial和网络资源理解理解，代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    ll mul = 1;
    for (int i = 1; i < n; i++)
        if (__gcd(i, n) == 1) {
            mul = mul * i % n;
            v.emplace_back(i);
        }
    mul %= n;
    if (mul != 1)
        for (auto it = v.begin(); it != v.end(); it++)
            if (*it == mul) {
                v.erase(it);
                break;
            }
    cout << v.size() << endl;
    for (int i = 0; i < v.size() - 1; i++) cout << v[i] << ' ';
    cout << v.back() << endl;
    return 0;
}