幂次进近【牛客tracker 每日一题】

幂次进近

时间限制：2秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定t tt次询问，每次询问给出两个正整数n nn和k kk。
请你找到最小的正整数m mm，使得n − m k n−m^kn−mk的绝对值最小。

输入描述：

第一行有一个整数t ( 1 ≤ t ≤ 10 5 ) t ( 1≤t≤10^5 )t(1≤t≤105)。
随后t tt行，每行两个整数n , k ( 1 ≤ n , k ≤ 10 18 ) n,k ( 1≤n,k≤10^{18} )n,k(1≤n,k≤1018)。

输出描述：

输出t tt行，每行一个正整数m mm。

示例1

输入：

3 6 2 1 1 78 3

输出：

2 1 4

示例2

输入：

3 114 514 1000000000 2 1000000000000000000 3

输出：

1 31623 1000000

解题思路

本题利用幂函数单调递增、绝对值代价函数呈单峰分布的特性，采用三分查找高效求解最优解，先定义快速幂函数计算m mm的k kk次幂，再构建代价函数f ( u ) f(u)f(u)统计n nn与u k u^kuk的绝对差值，以1 11为左边界、2 e 18 2e182e18开k kk次方为右边界搭建查找区间，通过三分法不断缩小区间范围至仅剩连续3 33个数值，最后遍历该区间内所有数值对比代价大小，选取对应最小代价的正整数m mm作为答案，该方案规避了暴力枚举的低效问题，单次查询时间复杂度极低，完美适配t ≤ 1 e 5 t≤1e5t≤1e5次查询且n 、 k n、kn、k上限达1 e 18 1e181e18的大数据场景，精准满足题目求最小绝对值对应m mm的核心需求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;ll n,k;llksm(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}returnres;}llf(ll u){returnabs(n-ksm(u,k));}voidsolve(){cin>>n>>k;ll num=2e18;ll l=1,r=pow(num,1.0/k);while(r-l>3){ll m1=l+(r-l)/3;ll m2=r-(r-l)/3;if(f(m1)>f(m2))l=m1;elser=m2;}ll ans=l;for(ll i=l;i<=r;i++){if(f(i)<f(ans))ans=i;}cout<<ans<<endl;}intmain(){ll t=1;cin>>t;while(t--)solve();return0;}