A. Anti-knapsack

题意

给你k和n，让你在1-n中找不重复的数组成一个集合，要求集合的任意子集的所有数字加起来不等于k，求最大的集合。

分析

首先，大于k的肯定可以放入集合（无论怎么加都是大于k的），k不能放入集合（否则k一个数组成的子集等于k），再考虑小于k的数，可以发现，拿所有大于等于k/2的数也都是可行的（任意两个数加起来都大于k，切每个数本身都小于k），代码就出来了。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        vector<int> ans;
        for(int i = k+1; i <= n; i++) ans.push_back(i);
        for(int i = k-1; i >= k-k/2; i --) ans.push_back(i);
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i++) printf("%d%c",ans[i],i == ans.size() - 1 ? '\n' : ' ');
    }
    return 0;
}

B. Planet Lapituletti

题意

告诉你一个地区的时间进位方式h,m（如h = 26,m = 50表示一天26小时，每小时50分钟），再告诉你现在的时间hh：mm，要求你找到离现在最近的一个时间点，满足镜面反射的时间也是合法的（即不超过h和m），若当天没有则可以跨越到第二天。

分析

首先，根据镜面反射的特点可知：0、1、8不变，2会变5,5会变2，其余的都是非法的。由于数据量不大，可以直接暴力每一分钟，每次检查一下这个时间点的镜面是否也合法即可。由于有前导零，镜面反射的时候会有影响（01遍10），推荐用字符串表示时间，计算的时候再转换成数字。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int h, m;
bool judge(char *t) {
    char s[10];
    memcpy(s,t,5);
    for(int i = 0; i < 5; i++) {
        if(i == 2) continue;
        if(s[i] == '2') s[i] = '5';
        else if(s[i] == '5') s[i] = '2';
        else if(s[i] == '3' || s[i] == '4' || s[i] == '6' || s[i] == '7' || s[i] == '9') return 0;
    }
    int x = (s[4] - '0') * 10 + s[3] - '0';
    int y = (s[1] - '0') * 10 + s[0] - '0';
    if(x < h && y < m) return 1;
    return 0;
}

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        char clo[10];
        cin >> h >> m >> clo;
        while(judge(clo) == 0) {
            int y = (clo[3] - '0') * 10 + clo[4] - '0';
            y++;
            if(y == m) {
                int x = (clo[0] - '0') * 10 + clo[1] - '0';
                x++;
                y = 0;
                if(x == h) x = 0;
                clo[0] = x/10+'0';
                clo[1] = x % 10 + '0';
            }
            clo[3] = y / 10 + '0';
            clo[4] = y % 10 + '0';
        }
        cout << clo << endl;
    }
    return 0;
}

D. GCD of an Array

题意

给你n个数存入数组a中，q次询问。每次询问给你i和x，表示将a[i]乘上x后，输出n个数的gcd。

分析

求n个数的gcd，我们假设这 n 个数的gcd为 p = 84 ，将 p 分解质因数后得到 p = 2 * 2 * 3 * 7 ，说明这n个数分解质因数后每个数也都包含 2 , 2 , 3 , 7 这几个质因数。也就是说，我们需要记录一下每个数的每个质因数j出现的次数k，然后记录一下每个质因数j出现k次的次数，如果出现k次的次数达到了n次，则表示每个数字都含有k个质因数j，那么gcd分解质因数后也会有k个质因数j，上述的两个记录可以通过两个map来实现。对于每次询问，会在 i 这个位置乘 x ，实际上就是给i这个位置贡献了若干个由x分解得来的质因数，维护一下map对应的值，再判断是否到达 n 次，如果到达 n 次则 gcd 乘上这个质因数（因为每次质因数j出现k次的次数只会有一次到达n次，所以不会重复计算）。

代码

#include <bits/stdc++.h>
using namespace std;

const long long N = 501000;
const long long mod = 1e9+7;

long long a[N], n, m;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
unordered_map<int,map<int,int>> mp,cnt;
long long ans = 1;
void solve(int pos, int x) {
    for (int j = 2; j <= sqrt(x); j++) {
        while (x % j == 0) {
            //第pos个位置对应的数中质因数j出现的次数+1
            mp[pos][j]++;
            //质因数j出现mp[pos][j]次的次数+1
            cnt[j][mp[pos][j]]++;
            //设mp[pos][j]= k
            //如果质因数j出现k次的次数达到n次，则说明gcd中有k个质因数j相乘，
            //但由于既然每个数中同时有k个j，那肯定也满足同时有k-1个j，
            //故这次只要将答案乘以j就行了，k-1个已经在之前乘过了。
            if (cnt[j][mp[pos][j]] == n) ans = (ans * j) % mod;
            x /= j;
        }
    }
    //别忘了x不为1的话也是一个质因数，处理方式同上
    if (x > 1) {
        mp[pos][x]++;
        cnt[x][mp[pos][x]]++;
        if (cnt[x][mp[pos][x]] == n) ans = (ans * x) % mod;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        solve(i,a[i]);
    }
    while (m--) {
        long long pos, mul;
        scanf("%d %lld",&pos, &mul);
        solve(pos,mul);
        printf("%lld\n",ans%mod);
    }
    return 0;
}