HDU 4430 Yukaris Birthday (二分+枚舉)

題意：給定一個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;  
}  

#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;
}