AB: 略
C:
可以转化为比较对数，然后直接模拟即可（long double 128位 表示范围\(-1.2 \times 10^{-4932}~1.2 \times 10^{4932}\)）
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//------------------------
int main(void)
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll p, q;
cin>>p>>q;
long double M=logl(1e18);
int n=2;
while(++n){
long double t=logl(p)*q;
if(t-M>0) break;
long long tem=pow(p, q);
p=q;
q=tem;
}
cout<<n-1<<endl;
return 0;
}
D：
tricks: 一共有两个属性，每个物品都有这两个属性，有两组物品，可以建立一个二维坐标系，来观察一下
- 猫猫的友善值作为横坐标，期望友善值作为纵坐标
- 主人的期望友善值作为横坐标，友善值作为纵坐标
- 将猫猫按照友善值从小到大排序，主人按照期望友善值从小到大排序。要求的答案就是对于每个猫猫，它的左上部分的主人的友善值的最大值。具体来说就是：遍历每一个猫猫，用指针遍历的方式遍历主人，取主人友善值的最大值，然后离线更新猫猫的答案
代码如下：
#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y, id;
};
bool cmp(node a, node b){
return a.x<b.x;
}
int main(void)
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin>>n>>m;
vector<node> a(n), b(m);
for(int i=0; i<n; i++) cin>>a[i].x;
for(int i=0; i<n; i++) cin>>a[i].y;
for(int i=0; i<n; i++) a[i].id=i;
for(int i=0; i<m; i++) cin>>b[i].y;
for(int i=0; i<m; i++) cin>>b[i].x;
sort(a.begin(), a.end(), cmp);
sort(b.begin(), b.end(), cmp);
vector<int> ans(n);
int mx=-1, last=0;
for(int i=0; i<n; i++){
while(last<m && b[last].x<=a[i].x){
mx=max(mx, b[last].y);
last++;
}
if(mx>=a[i].y) ans[a[i].id]=mx;
else ans[a[i].id]=-1;
}
for(int i=0; i<n; i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
E：
- a=b
- a=b=1，print 1
- a=b \(\neq\) 1 print 0
- a \(\neq\) b
- WLOG b>a，根据更相减损之术，有：
-
\[gcd(a+c, b+c) = gcd(a+c, b-a) = d \neq 1 \]
- 因此，枚举每一个b-a的因子d（可在\(O(\sqrt n)\)内完成），\(O(1)\) 算出使得\(d \mid a+c\)的最小c（具体来说就是， \((d-a\%d)\%d\) ）
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(ll a, ll d)
{
return (d-a%d)%d;
}
int main(void)
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll a, b;
cin>>a>>b;
if(a==b){
if(a==1) cout<<1<<endl;
else cout<<0<<endl;
return 0;
}
if(a>b) swap(a, b);
ll tem=b-a;
ll ans=-1;
for(ll i=1; i<=(ll)sqrt(tem); i++){
if(tem%i==0){
if(i!=1){
ll t=calc(a, i);
if(ans==-1) ans=t;
else ans=min(ans, t);
}
if(tem/i != 1){
ll t=calc(a, tem/i);
if(ans==-1) ans=t;
else ans=min(ans, t);
}
}
}
cout<<ans<<endl;
return 0;
}