2.4每日一题

题目链接：https://www.nowcoder.com/practice/1eda6676a6e544838263d8de9a8f3eed?channelPut=tracker2
心得：依旧是比较浅显的思路，二分快速幂，不过坑人的点在于精度，这道题不取模，且范围数极大，即使二分后最大值是1e9，但是幂次运算会导致精度爆炸，所以我们的快速幂模板要发生变化
快速幂plus模板：

点击查看代码

// limit: 你的目标上限（通常是 n，或者为了计算距离设为 n+n）
ll qpow(ll a, ll b, ll limit) {ll res = 1;// 【第一关：门槛检查】// 若底数本身已如高山仰止，超过了界限，且还需要乘（b>=1），那直接不用算了。if (a > limit) return limit + 2; while (b > 0) {// 【第二关：累积检查】(当 b 是奇数，需要把 a 乘进 res 里)if (b & 1) {// 问：res * a 会超吗？// 答：看 limit / res 是否小于 aif (limit / res < a) return limit + 2; res = res * a;}// 【第三关：进化检查】(a 自身翻倍：a = a * a)// 这一步最凶险，因为指数增长极快if (b > 1) { // 只有后面还需要用到 a 时，才计算新的 a// 问：a * a 会超吗？// 答：看 limit / a 是否小于 aif (limit / a < a) a = limit + 2; // 标记为无穷大else a = a * a; // 安全，放行}b >>= 1;}return res;
}

ac代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128;
ll qpow(ll a,ll b,ll limit){ll res=1;if(a>limit) return limit+2;while(b>0){if(b&1) {if(limit/res<a) return limit+2;res=res*a;}if(b>1){if(limit/a<a) a=limit+2;else a=a*a;}b>>=1;}return res;
}
bool check(ll mid,ll n,ll k){if(qpow(mid,k,n)>=n) return true;else return false;
}
void solve(){ll n,k;cin>>n>>k;if(k==1){cout<<n<<"\n";return ;}ll l=1,r=1e9;ll ans=1;while(l<=r){i128 mid=(l+r)>>1;if(check(mid,n,k)){ans=mid;r=mid-1;}else l=mid+1;}if(ans==1){cout<<"1\n";return ;}ll ans1=qpow(ans,k,n+n)-n;ll ans2=n-qpow(ans-1,k,n+n);if(ans1<ans2){cout<<ans<<"\n";}else cout<<ans-1<<"\n";}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}