补题 25届acm校队训练赛2

G 快速幂 算法(1) 如果将 a 自乘一次就会变成 a^2 。再把 a^2 自乘一次就会变成 a^4 。然后是 a^8…… 自乘 n 次的结果是 a^2n 。对吧……(2) a^xa^ya^xy这个容易。(3) 将 b 转化为二进制观看一下比如 b(11)10​ 就是 (1011)2​ 。从左到右这些 1 分别代表十进制的 8,2,1。可以 说 a^11a^8×a^2×a^1。快速幂 把指数看成二进制只在 1 的位置乘其他位置用平方跳过#includebits/stdc.h using namespace std; typedef long long ll; ll a,b,p; ll ans1,o; ll fast(ll a,ll b,ll p) { ll ans1; a%p; // 避免a的数据太大 while(b) { if(b%21) // if(b1) ans(ans*a)%p; a(a*a)%p; 将p拆分为二进制数 可以降低时间和空间 b/2; // b1; } return ans; } int main() { cinabp; ofast(a,b,p); printf(%lld^%lld mod %lld%lld,a,b,p,o); }F 第三边主要是 题目的理解244353597不能超过第三边#includebits/stdc.h using namespace std; typedef long long ll; ll n,t; ll sum; int a[200005]; int main() { ios::sync_with_stdio(false); cin.tie(0); ios::sync_with_stdio(false); cout.tie(0); cint; while(t--) { cinn; for(int i0;in;i) { cina[i]; } if(n1) couta[0]endl; else { sum0; for(int i0;in;i) { suma[i]; } coutsum-(n-1)endl; } } return 0; }J 跳石头 二分答案求最小值→mid (l r) / 2求最大值→mid (l r 1) / 2#includebits/stdc.h using namespace std; typedef long long ll; int n,m,L; int a[50005]; bool check(int x) { int t0,cnt0; for(int i0;in;i) { if(a[i]-tx) cnt; else ta[i]; } if(L-tx) cnt; return cntm; } int er(int l,int r) { while(lr) { int mid(lr1)/2; // 必须加一 不加一会陷入死循环 if(check(mid)) lmid; else { rmid-1; } } return l; } int main() { ios::sync_with_stdio(false); cin.tie(0); ios::sync_with_stdio(false); cout.tie(0); cinLnm; for(int i0;in;i) { cina[i]; } int anser(0,L); coutansendl; return 0; }