[乱搞]51 Nod 1859—Clarke and number

时间:2017-10-17 19:39:38

题目梗概

给定一个数,可以对这个数做一下两种操作:

x=xk

x=n2

用最小的步数使n->0。

解题思路

对于第二种操作,就是将x变为小于等于x的最大的平方数。

显然两种操作需要交替操作。

方法很简单,注意特殊情况就可以了。

#include<cstdio>
#define LL long long
using namespace std;
int k,T;
LL n,ans;
int main(){
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%lld%d",&n,&k);
        if (k==2&&n%2==1&&n<=4){printf("-1\n");continue;}
        if (k==2&&n==5){printf("3\n");continue;}
        if (n==0){printf("0\n");continue;}
        LL L=0,R=1e9,mid;
        while(L<=R){
            mid=L+(R-L>>1);
            if (mid*mid<=n) L=mid+1,ans=mid;else R=mid-1;
        }
        if (k==1) printf("%lld\n",ans*2-(ans*ans==n));else{
            if (n<=4) printf("%lld\n",n/2);else
            printf("%lld\n",2*(ans-1)-1+2-(n-ans*ans<=1));
        }
    }
    return 0;
}
作者:CHN_JZ 发表于2017/10/17 21:39:38 原文链接
阅读:25 评论:0 查看评论