牛客多校训练4：B和H题解

B Basic Gcd Problem

传送门：https://ac.nowcoder.com/acm/contest/5669/B

题目大意：
就是求那个函数值，题目很清楚。

解题思路：
题我的思路是：最后的答案一定是输出的 的幂（至于怎样判断的，可以带几个数试试，），然后就是确定这个幂的指数，我的方法是先预处理出所有数的最大因子
（1）只要这个最大因子不是 ，指数就要加 ；
（2）接着找这个最大因子的最大因子是不是 ，不是 的话继续上面（1）的操作；如果最大因子是 的话就输出答案：（ 指的是上述加的 的个数,用正规语言来说就是迭代次数）

这道题需要用线性筛来预处理每个数的最大因子是谁，在线性筛的模板中中稍加一些需要维护的信息就好。还需要用到快速幂，套版子就行，注意的一点就是，会爆,要小心，这个坑当时WA了一次。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int mod = 1e9+7;
int f[N];//f[i]表示i的最大因子
int prime[N],cnt;
int vis[N];
void init() {
    f[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i])
        {
            prime[cnt++] = i;
            f[i] = 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            f[i * prime[j]] = max(f[i * prime[j]],i);
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int t;
    init();
//    for(int i=1;i<=20;i++)
//    {
//        if(!vis[i])
//        cout<<i<<" ";
//     } 
    scanf("%d",&t);
    while(t--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==1)
        {
            cout << 1 << endl;
        }
        else{
            int tmp=f[x];
            int cnt=1;
            while(tmp!=1)
            {
                tmp=f[tmp];
                cnt++;
            }
            printf("%d\n",qpow(y,cnt)%mod);
        }
    }
    return 0;
}

H Harder Gcd Problem

传送门：https://ac.nowcoder.com/acm/contest/5669/H

题目大意：
给定整数 ,用 ~ 中的整数来构造出两个最大的集合 和 每个整数只能用一次,并且要使两个集合相对应的位置不互质，即题目所说的 .输出最大匹配对数和匹配方案。

解题思路：
看了直播的讲解，讲得很清晰，忍不住赞叹一句，妙啊！太妙了！.接下来，我将我从直播中学到的再来复述一遍。

排除一定不会出现的数

数字 一定不出现在匹配的方案中；

大于 的质数一定不会出现在方案中；

贪心策略

倒叙枚举从 到 中所有的质数的倍数（至于为什么倒叙，在编写代码的时候就能体现出来，会简便许多,这样可以保证每个质数的 倍是第一次出现）

优先处理质数 的 倍，暂时跳过 的 倍，对于 的倍数两两之间可以随意匹配，都是满足条件的，如果 的倍数在 的范围内的且没有匹配过的个数是偶数个的话（包括 的 倍），那么将这些数全部存入答案即可；如果是奇数个（包括 的 倍），就将 的 倍的那个数先存储起来，这里我将其存入 数组中，注意：存入 数组中的p的2倍的数都要先标记为已匹配过的数;避免在处理其他质数的时候发生冲突，比如枚举 的 倍是 ，在枚举 的倍数时， 的 倍也是 ，此时在枚举 的这一轮， 这个数字是不需要考虑在内的,这个 要么就在没举 的时候直接计入答案，要么存入质数的 倍的那个数组中

最后处理质数的 倍的这个数组，这个数组中的数字两两之间都是可以匹配的，因为都有 这个因子,所以 一定不会等于 .

最后就是代码的编写了，注意初始化和标记，还有就是细节，初始化需用到线性筛来求质数。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;
int prime[N],cnt;
bool vis[N];
void init() {
    for (int i = 2; i < N; i++) {
        if (!vis[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
bool flag[N];//标记是否还能进行匹配 
int main()
{
    int t;
    vector<PII> ans;//存储互相匹配的答案  
    vector<int> st;//存储多余的质数p的二倍  
    vector<int> tmp;//存储质数p的倍数  
    init();
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n); 
        memset(flag,false,sizeof flag); 
        ans=vector<PII> ();
        st=vector<int> ();

        for(int i=n/2;i>=2;i--)
        {
            if(vis[i]) continue;//合数直接跳过
            int count1=0;
            tmp=vector<int> ();
            for(int j=1;j*i<=n;j++)
            {
                if(!flag[j*i]&&j!=2){
                    count1++;
                    tmp.push_back(j*i);
                } 
            }
            if(count1%2==0)
            {
                for(int j=0;j<tmp.size();j+=2)
                {
                    ans.push_back({tmp[j],tmp[j+1]});
                    flag[tmp[j]]=true;
                    flag[tmp[j+1]]=true;
                }
                st.push_back(2*i);
                flag[2*i]=true;
            }
            else{
                ans.push_back({tmp[0],2*i});
                flag[tmp[0]]=true;flag[2*i]=true;
                for(int j=1;j<tmp.size();j+=2)
                {
                    ans.push_back({tmp[j],tmp[j+1]});
                    flag[tmp[j]]=true;
                    flag[tmp[j+1]]=true;
                }
            }
        } 
        if(st.size()>=2)
        {
            if(st.size()%2==0)
            {
                for(int i=0;i<st.size();i+=2)
                {
                    ans.push_back({st[i],st[i+1]});
                    flag[st[i]]=true;
                    flag[st[i+1]]=true;
                }
            }
            else{
                for(int i=1;i<st.size();i+=2)
                {
                    ans.push_back({st[i],st[i+1]});
                    flag[st[i]]=true;
                    flag[st[i+1]]=true;
                }
            }
        }
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++)
        {
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }
    }    
    return 0;
} 

CSDN 这两题博文，欢迎来访，https://blog.csdn.net/qq_45660232/article/details/107474344