2020牛客暑期多校训练营（第四场）
同写着自己看
B,Basic Gcd Problem
我贴一下题目吧，当时我一看这一场这些题目，我还以为我要爆零了
这个式子看起来很牛比，但是实际上理解之后就明白了，这个题目一看就是要找最大的gcd，那怎么找呢，一个数很容易就能想到和比自己小的数里面gcd最大的就是自己最大的因数，因为gcd得到的一定是那个数的因数，所以最大的就是那个数最大的因数，然后又对那个对大的因数找最大的因数，最后会找到1，每找一次就乘以一个c，所以答案就是找了多少次就是c的几次方
然后就是我自己做的时候，我第一次做的时候是采用的顺推，就是每输入一个数就找一次，最后不负众望的超时了，所以我后来就改成先预处理好，然后直接输出就好了
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll n=1e6+5;
const ll mod=1e9+7;
ll is_prime[n];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int cao(int x){
int n = sqrt(x)+3;
for(int i = 2 ; i <= n ; ++i)
if(x % i == 0) return x/i;
return 1;
}
int main (void){
int T;
for(int i = 2 ; i <= n ; ++i)
is_prime[i] = is_prime[cao(i)]+1;
scanf("%d",&T);
while(T--){
int a,b;
scanf("%d%d",&a,&b);
printf("%lld\n",qpow(b,is_prime[a])%mod);
}
return 0;
}F,Finding the Order
这个题目才是真的签到题，告诉你两个线上四个点的距离，然后去推测c在前面还是d在前面，没啥好说的代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll n=1e6+5;
const ll mod=1e9+7;
int main(void){
int T;
scanf("%d",&T);
while(T--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int cnt;
cnt=max(max(a,b),max(c,d));
if(cnt==c||cnt==b)
printf("AB//CD\n");
else
printf("AB//DC\n");
}
return 0;
}
