目录
https://www.luogu.com.cn/contest/90215#problems
P8813 [CSP-J2022] 乘方
- 题目描述很简单，但是数据范围很大, \(a,b \in [1,10^9]\)。
- 一眼 long long 快速幂，可AC
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f, M=1e9;
LL fpow(LL a,LL n) {
LL ans=1;
while(n) {
if(n&1) ans=ans*a;
if(ans > M || ans<=0) return -1;
a = a*a;
n>>=1;
}
return ans;
}
int main() {
LL a,b;
while(cin>>a>>b) {
cout<<fpow(a,b)<<endl;
}
fclose(stdin); fclose(stdout); return 0;
}
P8814 [CSP-J2022] 解密
-
一元二次方程复习
-
一元二次方程：\(ax^2+bx+c=0\)，已知 \(a,b,c\)，求解 \(x\)。
-
公式：\(\Delta=b^2-4ac\)
-
如果 \(\Delta < 0\)，则无解。
-
如果 \(\Delta=0\)，则有唯一解 \(x=\frac{-b}{2a}\)
-
如果 \(\Delta>0\)，则有两个不同的解 \(x=\frac{-b±\sqrt{\Delta}}{2a}\)
-
题意：\(p*q=n, e*d=(p-1)(q-1)+1\)，已知 \(n,e,d\)，求 \(p,q\)。
-
推导
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f, M=1e9;
LL k,n,e,d;
int main(){
cin>>k;
for(int i=1; i<=k; i++) {
cin>>n>>e>>d;
LL x = n+2-e*d;
LL dx = x*x - 4*n;
if(dx < 0) cout<<"NO"<<endl;
else {
LL q1 = (x-(int)sqrt(dx)) /2;
LL q2 = (x+(int)sqrt(dx)) /2;
LL p1 = n/q1, p2 = n/q2;
if(p1 > q1) swap(p1,q1);
if(p2 > q2) swap(p2,q2);
int flag=0;
if(p1*q1==n && p1+q1==x) cout<<p1<<" "<<q1<<endl, flag=1;
if(!flag && p2*q2==n && p2+q2==x) cout<<p2<<" "<<q2<<endl, flag=1;
if(flag==0) cout<<"NO"<<endl;
}
}
fclose(stdin); fclose(stdout); return 0;
}
- 方法2：二分答案
- 二分查询 \(p\)， $O(1) $ 检查 \(p,q\) 是否满足，整体复杂度 \(O(nlogn)\)， 可以AC