Finding the Order
链接:https://ac.nowcoder.com/acm/contest/5669/F
思路比较简单,有关图形的题目还是要多动手。
• 找到这四个距离的最大值。
• 如果最大值来自 AD 或 BC,则 AB//CD,否则 AB//DC。

#include<iostream>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int a, b, c, d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        puts(max(b,c)>=max(a,d)?"AB//CD":"AB//DC");
    }
}

Basic Gcd Problem
链接:https://ac.nowcoder.com/acm/contest/5669/B
这类题目应该先在纸上推一推,找一找规律或者转换一下题目的形式。这道题目如果能够发现
f(x)=c^(x的质因子个数),剩下的内容就比较容易了

#include<cstdio>
#define ll long long
using namespace std;
const int mod=1e9+7;
int main(){
    int t,c,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&c);
        ll ans=1;
        for(int i=2;i*i<=n;i++)
            while(n%i==0){
                n/=i;
                ans=ans*c%mod;
            }
        if(n>1)    ans=ans*c%mod;
        printf("%lld\n",ans);
    }
    return 0;
} 

Harder Gcd Problem
链接:https://ac.nowcoder.com/acm/contest/5669/H
看了一下CSDN上的题解,这道题的解法还是非常多的。不过个人觉得还是贪心的思路更为简洁简单。
思路:因为一个素数越大,与他匹配的数就会越少,所以考虑优先匹配较大的素数。
这样保证每个含因子是该素数的尽可能被匹配到,因为是一组是两个数,所以当满足条件的数的为奇数个时,显然我们要扔掉一个看是否能和其他数匹配,显然能与最小的质数2匹配的数是最多的,所以我们保留一下是2的倍数的数,如果已经匹配了奇数个,就直接把它给该素数作为贡献,否则给2的倍数进行匹配。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int p[N],n,t,cnt,ans[N],tot;
bool a[N],vis[N];
void pre(){
    int n=2e5;
    for(int i=2;i<=n;i++){
        if(!a[i]) p[cnt++]=i;
        for(int j=0;j<cnt&&i*p[j]<=n;j++){
            a[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}
int main(){
    pre();
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);tot=0;
        for(int i=1;i<=n;i++) vis[i]=0;
        int pos=upper_bound(p,p+cnt,n/2)-p-1;
        for(int i=pos;i;i--){
            for(int j=p[i];j<=n;j+=p[i]){
                if(vis[j]||j==(p[i]<<1)) continue;
                ans[++tot]=j,vis[j]=1;
            }
            if(tot&1) vis[(p[i]<<1)]=1,ans[++tot]=(p[i]<<1);
        }
        printf("%d\n",tot>>1);
        for(int i=1;i<=tot;i+=2) printf("%d %d\n",ans[i],ans[i+1]);
    }
    return 0;
}