牛客暑期多校第四场

B.Basic Gcd Problem

题目链接

标签

数学 数论

解题思路

怎样才会最长呢，就是分解成若干个质数就好了，所以答案就为$c^k$k为n的质因数的个数

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
bool is_prime[MAXN];
vector<int> pri;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    is_prime[1]=1;
    for (int i = 2; i < 1e4; i++)if(is_prime[i]==0){for (int j = i*2; j <=1e4 ; j+=i)is_prime[j]=1;pri.push_back(i);}
    int T,n,c;
    cin>>T;
    while (T--)
    {
        cin>>n>>c;
        ll res=1;
        for (int i = 0; n!=1&&pri[i]*pri[i]<=n; i++)
        {
            while(n%pri[i]==0)
            {
                n/=pri[i];
                res=(res*c)%MOD;
            }
        }
        if(n!=1){res*=c;res%=MOD;}
        cout<<res<<endl;
    }
    
    return 0;
}

F.Finding the Order

题目链接

标签

思维 数学

解题思路

由于三角形两边之和大于第三边

$$
|AE|+|EC|>|AC| \tag 1
$$

$$
|BE|+|ED|>|BD| \tag{2}
$$

由(1)(2)得

$$
|BC|+|AD|>|AC|+|BD|
$$

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    int T;
    cin>>T;
    int ac,ad,bc,bd;
    while (T--)
    {
        cin>>ac>>ad>>bc>>bd;
        if(bc+ad>ac+bd)cout<<"AB//CD"<<endl;else cout<<"AB//DC"<<endl;
    }
    
    return 0;
}

H.Harder Gcd Problem

题目链接

解题思路

先对大质数的奇数数倍匹配，如果只有奇数个，那么凑一个偶数给他，最后剩余的偶数自由配对

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)2e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int is_prime[MAXN];
vector<int> prime;
void pre()
{
    is_prime[1]=1;
    for (int i = 2; i < MAXN-5; i++)if(is_prime[i]==0){for (int j = i*2; j <=MAXN-5 ; j+=i)is_prime[j]=1;prime.push_back(i);}
}
int a[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    int T,n;
    pre();
    cin>>T;
    while (T--)
    {
        cin>>n;
        int res=0;
        MEM(a,-1);
        int cur=upper_bound(all(prime),n*2)-prime.begin();
        if(cur>=prime.size())cur=prime.size()-1;
        for (int i = cur; i >0; i--)
        {
            int flag=-1;
            int x=prime[i];
            for (int j = n/x%2?n/x:(n/x-1); j >0; j-=2)
            {
                if(a[x*j]==-1)
                {
                    if(flag==-1)flag=x*j;
                    else
                    {
                        a[x*j]=flag;
                        a[flag]=x*j;
                        flag=-1;
                        res++;
                    }
                }
            }
            if(flag!=-1&&n/x>=2)
            {
                a[x*2]=flag;
                a[flag]=x*2;
                res++;
            }
        }
        int flag=-1;
        for (int i = 2; i <= n; i+=2)
        {
            if(a[i]==-1)
            {
                if(flag==-1)flag=i;
                else
                {
                    a[i]=flag;
                    a[flag]=i;
                    flag=-1;
                    res++;
                }
                
            }
        }
        cout<<res<<endl;
        for (int i = 1; i <= n; i++)
        {
            if(a[i]>i)cout<<a[i]<<" "<<i<<endl;
        }
        
    }
    
    return 0;
}