2020牛客暑期多校训练营（第四场）

2020牛客暑期多校训练营（第四场）
这场属实有点难受
@[toc]

A Ancient Distance

B Basic Gcd Problem

爷被卡自闭了

题目

仔细分析题其实就是问c^f（x）^等于等于多少
而f（x）等于什么呢？
唯一分解定理

而我们要做的就是求出f（x）=a1+a2+a3+....an
pow（c,sum）
我被int和longlong卡了，快速幂我用的longlong结果超时了
其实思路不难，多注意细节

代码：

#include <iostream>
#include <stdio.h>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+3;
const ll mod=1e9+7;
ll sum=0;
ll spr[maxn],zs[maxn],ds[maxn];
inline ll poww(ll a,ll b,ll p)
{
    ll res=1;
    ll base=a%p;
    while(b){
        if(b&1){
            res=(res*base)%p;
        }
       base=( base*base)%p;
        b>>=1;
    }

    return res%p;
}
//template <typename T>
//inline void read(T &s){
//     T t=1; char k=getchar(); s=0;
//    for (;k<'0'||k>'9';k=getchar()) if (k=='-') t=-1;//判断该数正负
//    for (;k>='0'&&k<='9';k=getchar()) s=(s<<1)+(s<<3)+(k^48);//<<1加上<<3就相当于*10，但是位运算的速度较快，^48也相当于-‘0’，同理，较快。
//    s*=t;
//}
//void olp(){ //先打表，欧拉筛
//    memset(is,true,sizeof is);
//    is[0] = is[1] = 0;
//    for(int i=2;i<maxn;i++){
//        if(is[i]) spr[cnt++]= i;
//        for(int j=0;i*spr[j]<maxn&&j<cnt;j++){
//            is[i*spr[j]] = 0;
//            if(i%spr[j]==0) break;
//        }
//    }
//}
void fj(int x){ //不同素数的个数
    for(int i=2;i*i<=x;i++){
       while(x%i==0)
       {
           x/=i,sum++;       
       }
    }
    if(x!=1){ //如果分解玩x都不等于1，那么x必定是一个素数
        sum++;
    }
    return ;
}
int main(){
    //olp();
        int t;
    scanf("%d",&t);
        while(t--)
    {

         ll n,c;
       scanf("%lld%lld",&n,&c);
    //  cout<<n<<" "<<c<<endl;
        sum=0;
        fj(n);
        ll ww=poww(c,sum,mod);
        printf("%lld\n",ww);
    }

    return 0;
}

C Count New String

D Dividing Strings

E Eliminate++

F Finding the Order

题意：

两条平行直线，上一条是ab（a在左边，b在右边），下一条是dc（但是d和c谁在左谁在右未知）
现在给你，ac，ad，bc，bd的长度，问d和c谁在左谁在右

题解：

画图分析一下
三种情况：cd正常，c很远，d很远
图中是cd的情况
而dc的情况刚好相反

代码：

#include<bits/stdc++.h>
#define rg register
using namespace std;
//  scanf("%d",);
//  printf("%d",);
int gcd(int a,int b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main()
{
    int t;
    t=read();
    while(t--)
    {
        int ac=read(),ad=read(),bc=read(),bd=read();
        if(ac<=ad&&bc>=bd)
        {
            printf("AB//CD\n");
        }
        else if(ac>=ad&&bc>=bd&&ac<bc)
        {
            printf("AB//CD\n");
        }
        else if(ac<=ad&&bc<=bd&&ad>bd)
        {
            printf("AB//CD\n");
        }
        else printf("AB//DC\n");
    }
    return 0;
}

//printf("AB//CD\n");
//printf("AB//DC\n");

G Geometry Challenge

H Harder Gcd Problem

I Investigating Legions

J Jumping on the Graph