F、Finding the Order

题意：已知AB//CD，给出AD，AC，BD，BC的长度，判断是AB//CD还是AB//DC。
思路：将各种情况画出来，进行分类即可。如果AD或者BC长为四条边最长的，那么就是AB//CD，否则为AB//DC。
代码：

#include<iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int ac,ad,bc,bd;
        cin>>ac>>ad>>bc>>bd;
        if(ad>=ac&&ad>=bc&&ad>=bd)  cout<<"AB//CD"<<endl;
        else if(bc>=bd&&bc>=ac&&bc>=ad)  cout<<"AB//CD"<<endl;
        else  cout<<"AB//DC"<<endl;
    }
    return 0;
}

B、Basic Gcd Problem

题意：图片说明
思路：通过模拟我们可以发现，最后的答案就是,最后对答案取模即可。先通过预处理将1e6之前质因子都求出来。
代码：

#include<iostream> 
#include<cmath>
#include<cstring>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
bool inq[1000010]={false};
ll f[1000010];
void inti(){
    f[1]=1;
    for(int i=2;i<=1e6+7;i++){  //预处理
        if(inq[i]==false){
            f[i]=i;
            for(int j=i+i;j<=1e6+7;j+=i){
                if(!f[j])   f[j]=i;  //记录每个数的最小的质因子
                inq[j]=true;
            }
        }
    }
}
int main(){
    inti();
    int t;
    scanf("%d",&t);
    while(t--){
        ll n,c;
        scanf("%ld%ld",&n,&c);
        ll ans=1;
        while(n!=1){
            ans=ans*c%mod;
            n/=f[n];
        }
        cout<<ans<<endl;
    }
    return 0;
}

H、 Harder Gcd Problem

题意：从1-n里面选择最多的组合，使得每个组合的两个数的最大公因数不为1。输出组合的个数和这些组合的可能情况
思路：贪心+STL+数论。枚举小于n/2的质因数，按从大到小的顺序进行枚举，首先，我们说说为什么要枚举质因数，我们发现，不管是那个数，都是可以由一个质数乘若干倍而得到的（这个知道埃式筛的同学就可以理解），为了让配对的数量尽可能多，我们应该尽量的使两个数的gcd尽可能的小，当然，也不一定不是最小的就不可以（这个后面会说到），然后，枚举小于n/2的就不用多说了吧，和上面是一个道理的。接着，我们来讨论为什么要进行从大到小的顺序进行枚举，我们又可以发现，对于两个不同的质数a,b，如果a>b，那么在相同的范围内，可以与a进行合法配对的数的数量一定不会多于与b进行合法配对的数的数量，即你的数越小，与你配对的数的数量就越多（大于等于）。为了使得最后的配对数量尽可能的多，我们肯定要优先照顾那些更不可能配对的数。总之，我感觉还是要对埃式筛有个更加深入的理解。
那么，倘若一个质数，与它进行合法配对的数的数量是个奇数，那么肯定会多出一个数来，多出哪个呢？那肯定是多出它的一倍的那个数，即2*p,还是那个道理，我们有多出两倍的，多出三倍的，多出n倍的，那肯定要优先考虑先将大的数进行配对成功。暂时将小的先留下。当然，肯定不能够留下自身，因为它本身就是个质数。注意，之前配对成功的数不能再进行配对了。
接下来，说说怎么写代码？
先进行预处理，我们先找出2e5+10/2范围内的所有的质因数放到一个数组里面去，然后，我们可以输入n之后找到小于等于n/2的最大的那个质因数，然后就可以反向枚举啦，枚举到每个质因数p的时候，我们先遍历一遍可以和这个质因数配对的所有的数，这里我用的是一个set容器，因为这样可以更加方便地删除2p，如果遇到了数量是奇数地的情况。是奇数就删除2p，然后就可以进行一个任意的配对了，我是按照顺序进行两两配对的，用的是一个vector里面套了一个pair容器。最后只要输出vector的大小和里面的元素即可。
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int pnum=0;
bool inq[maxn]={false};
bool vis[maxn]={false};
int primer[maxn];
vector<pair<int,int> > v;
void inti(){  //预处理
    for(int i=2;i<=maxn/2;i++){
        if(inq[i]==false){
            primer[pnum++]=i;
            for(int j=i+i;j<=maxn/2;j+=i){
                inq[j]=true;
            }
        }
    }
}
int main(){
    inti();
    int t;
    cin>>t;
    while(t--){
        v.clear();
        memset(vis,false,sizeof(vis));
        int n;
        cin>>n;
        int k=upper_bound(primer,primer+pnum,n/2)-primer;  //找到primer数组里面第一个大于n/2的数的位置
        for(int i=k-1;i>=0;i--){
            set<int> st;
            for(int j=primer[i];j<=n;j+=primer[i]){  //这个就是一个埃式筛的思想
                if(vis[j]==false)  st.insert(j);
            }
            if(st.size()&1)  st.erase(2*primer[i]);
            set<int>::iterator it=st.begin();
            //int len=st.size();
        //    cout<<"len:"<<len<<endl;
            int a,b;
            for(;it!=st.end();it++){
                a=*it;
                it++,b=*it;
                v.push_back(make_pair(a,b));
                vis[a]=true;
                vis[b]=true;
            }
        }
        int m=v.size();
        cout<<m<<endl;
        for(int i=0;i<m;i++){
            cout<<v[i].first<<" "<<v[i].second<<endl;
        }
    }
    return 0;
}