HDU 4430 Yukari's Birthday (二分+枚举)

男娘i 2021-12-14 00:35 533阅读 0赞

题意：给定一个n（18 ≤ n ≤ 10^12），一个等比数列k + k^2 + .......+ k^r = n 或者 = n-1，求出最小的k\*r，如果最小的不唯一，则取r更小的

分析：两个未知数，r,k，很明显，r的范围只有几十而已，所以枚举r；k的范围很大，需要二分...................

二分k的上界依情况而定 ： pow(n,1.0/i)；

#include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <set>
    #include <queue>
    #include <stack>
    #include <climits>//形如INT_MAX一类的
    #define MAX 100005
    #define INF 0x7FFFFFFFFFFFFFFF
    #define REP(i,s,t) for(int i=(s);i<=(t);++i)
    #define ll __int64
    #define mem(a,b) memset(a,b,sizeof(a))
    #define mp(a,b) make_pair(a,b)
    #define L(x) x<<1
    #define R(x) x<<1|1
    # define eps 1e-5
    //#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
    using namespace std;
    __int64 n;
    
    struct node {
        __int64 k,ans;
        int r;
    }minn;
    
    __int64 pow2(__int64 mid,int r) {
        __int64 t = mid;
        for(int i=0; i<r-1; i++) {
            mid *= t;
        }
        return mid;
    }
    
    __int64 search(int r,__int64 tmp,__int64 high) {
        __int64 low = 2,mid;
        while(low <= high ) {
            mid = (low + high) >> 1;
            __int64 cal = (pow2(mid,(r+1)) - mid) / (mid-1);
            //cout << "k: " << mid << " r: " << r << " cal: " << cal << endl;
            if(cal > tmp) {
                high = mid - 1;
            } else if(cal < tmp) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    
    int main(){
        while(cin >> n) {
            int high = log(n) / log(2);
            minn.ans = n-1;
            minn.r = 1;
            minn.k = n-1;
            for(int i=2; i<=high; i++) {
                int tmp = pow(n,1.0/i);
                __int64 tmp1 = search(i,n,tmp);
                __int64 tmp2 = search(i,n-1,tmp);
               // cout << "i: " << i << " tmp: " << tmp << " tmp1: " << tmp1 << " tmp2: " << tmp2 << endl;
                if(tmp1 != -1 && i * tmp1 <= minn.ans) {
                    if(tmp1 * i == minn.ans && i < minn.r) {
                        minn.r = i; minn.k = tmp1;
                    } else if(i * tmp1 < minn.ans){
                        minn.ans = i * tmp1; minn.r = i; minn.k = tmp1;
                    }
                }
                if(tmp2 != -1 && i * tmp2 <= minn.ans) {
                    if(tmp2 * i == minn.ans && i < minn.r) {
                        minn.r = i; minn.k = tmp2;
                    } else if(i * tmp2 < minn.ans){
                        minn.ans = i * tmp2; minn.r = i; minn.k = tmp2;
                    }
                }
            }
            printf("%d %I64d\n",minn.r,minn.k);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3271102.html