多校4(BFH)_牛客博客

B.Basic Gcd Problem(质因数分解）

思路：考虑 $c$ 的贡献次数，我们最后的答案肯定是： $c^{cnt}$ 形式，所以我们只需求出 $cnt$ 。

$ep:n=16,c=5$ 。

显然 $f_c(16)=c\times max\{f_c(i)\},i\in\{1,2,4,8\}$ 。

$f_c(1)=1$

$f_c(2)=c\times max\{f_c(i)\},i\in\{1\}\rightarrow f_c(2)=c$

$f_c(4)=c\times max\{f_c(i)\},i\in\{1,2\}\rightarrow f_c(4)=c^2$ 。

$f_c(8)=c\times max\{f_c(i)\},i\in\{1,2,4\}\rightarrow f_c(8)=c^3$ 。

所以 $f_c(16)=c^4,cnt=4$ 。

看了上面这个样例你可能已经发现了 $cnt$ 跟因数有关系。

因为我们要让 $cnt$ 尽可能大，所以我们需要尽可能多的进行相乘转换。

我们换个方式考虑： $n=16=2^4$ 。

$1\times2=2,2\times2=4,4\times2=8,8\times2=16$ 。

这样是不是很显然了。

再来： $ep:n=60=2^2\times3\times 5$ 。

$1\times 2=2，2\times2=4,4\times3=12,12\times5=60$ 。

显然按照质因数分解后的个数依次相乘 $cnt$ 是最大的。

即答案就是质因数个数之和。

接下来就很简单了，可以考虑直接暴力 $O(\sqrt{n})$ 一边分解一边计算贡献，或者预处理一波每个数的对应素数。 $O(logn)$

总复杂度： $O(T\sqrt{n})$ 或 $O(nloglogn+Tlogn)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,c;
        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;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
bool a[N];
int b[N],p[N];
void Ess(){
     int cnt=0;
     int n=1e6;
     a[1]=true;
     for(int i=2;i<=n;i++)
     {
        if(!a[i]) p[cnt++]=i,b[i]=i;
        for(int j=0;j<cnt&&i*p[j]<=n;j++)
        {
            a[i*p[j]]=true,b[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
     }
}
ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    int t;
    Ess();
    scanf("%d",&t);
    while(t--){
        ll n,c;
        scanf("%lld%lld",&n,&c);
        if(!a[n]) printf("%lld\n",c%mod);
        else {
            int cnt=0;
            while(n!=1){
                n/=b[n];
                cnt++;
            }
            printf("%lld\n",ksm(c,cnt));
        }
    }
    return 0;
}

F.Finding the Order(数学)

思路：小学数学知识。

显然梯形的四边形对角线之和要大于两腰之和。
图片说明

证明： $\because OA+OD>AD,OB+OC>BC\\ \therefore (OA+OC)+(OB+OD)>AD+BC\\ \therefore AC+BD>AD+BC$

所以只需要判断一下 $b+c$ 是否 $>a+d$ 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        puts(b+c>a+d?"AB//CD":"AB//DC");
    }
    return 0;
}

H.Harder Gcd Problem(贪心)

思路：考虑每个素数对答案的贡献.

因为一个素数越大，与他匹配的数就会越少，所以考虑优先匹配较大的素数。

这样保证每个含因子是该素数的尽可能被匹配到，因为是一组是两个数，所以当满足条件的数的为奇数个时，显然我们要扔掉一个看是否能和其他数匹配，显然能与最小的质数 $2$ 匹配的数是最多的，所以我们保留一下是 $2$ 的倍数的数，如果已经匹配了奇数个，就直接把它给该素数作为贡献，否则给 $2$ 的倍数进行匹配。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
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;
}