2020牛客多校第四场BFH题解

B. Basic Gcd Problem

找规律签到，易发现结果就是c的【n的质因数的个数】次方再mod 1e9+7。快速幂解决。

F. Finding the Order

签到。给定AC，AD，BC，BD四个点的距离，问是AB//CD还是AB//DC。
我的方法，固定AB及其中垂线位置。判断C在AB左方还是右方，之后根据BC和BD关系判断D在C的哪个方向。

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

int main() {
    int t; cin >> t;
    while(t--) {
        int AC,AD,BC,BD;
        cin>>AC>>AD>>BC>>BD;
        int ans=0;
        if(AC<BC) {
            if(AD<BD) {
                if(BC>BD) ans=1;
                else ans=0;
            }
            else ans=1;
        } else if(AC==BC) {
            if(AD>BD) ans=1;
        } else {
            if(AD>BD && AC<AD) ans=1;
        }
        if(ans) puts("AB//CD");
        else puts("AB//DC");
    }
}

还有很多种方法，这里列出大佬们的一个简洁代码。

#include <cstdio>
int T,a,b,c,d;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        puts(b+c>a+d?"AB//CD":"AB//DC");
    }
}

H. Harder Gcd Problem

题意

• 把 1~N 的数选尽量多的组，使得每组 gcd 大于 1。
• 输出任意一种方案。

题解

• 2p>n 的 p 必然不能匹配，将它们除去。
• 倒序枚举所有质因子 p，考虑所有是 p 的倍数且未被匹配的数，任意将它们进行匹配。
• 如果个数是奇数就不选 p*2。（尽量贪心地保证不选的数之后还能得到匹配）

#include <bits/stdc++.h>
#define show(x) std::cerr << #x << "=" << x << std::endl
using namespace std;

const int maxn = 1e6 + 5;
int v[maxn], prime[maxn], ans[maxn];
bool vis[maxn];
int m, n;

void primes(int n) { //素数线性筛
    memset(v,0,sizeof(v));
    m = 0;
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) {
            v[i] = i;
            prime[++m] = i;
        }
        for(int j = 1; j <= m; j++) {
            if(prime[j] > v[i] || prime[j] > n/i) break;
            v[i * prime[j]] = prime[j];
        }
    }
//    for(int i = 1; i <= m; i++) {
//        printf("%d ",prime[i]);
//        mp[prime[i]] ++;
//    }
}
int main() {
    primes(2e5+100);
    int t; scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        int id = 0;
        int pos = upper_bound(prime+1, prime+m+1, n/2) - prime - 1;
//        show(pos);
        for(int i=pos; i>0; i--) {
            for(int j=prime[i]; j<=n; j+=prime[i]) {
                if(vis[j] || j == (prime[i]<<1)) continue; // 特判2p，最后加入
                ans[id++] = j;
                vis[j]++;
            }
            if(id&1) ans[id++]=(prime[i]<<1), vis[ans[id-1]]++;
        }
        printf("%d\n",id/2);
        for(int i=0; i<id; i+=2) {
            printf("%d %d\n", ans[i], ans[i+1]);
        }
    }
}