二分搜索 UVALive 6076 Yukari's Birthday (12长春K)
2024-09-10 01:33:33
题意:问使得sum (k^i) = n || n -1 (1 <= i <= r) 的min (r*k)组合的r和k
分析:r的最大不会超过40,枚举r,二分搜索k。注意会爆long long,所以上界需要优化。r = 2开始上界就小于1e6,cyd将后面的范围也求出来了,其实1e6就够用了。
这水题卡了我好久,没有很好分析题目,做不出来就有种无力感,开始烦躁起来。还是题目做得少了,如果这种题做多了,可能看一眼就能做出来了。
/************************************************
* Author :Running_Time
* Created Time :2010-1-16 12:18:59
* File Name :K.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
ll n, r, k; ll cal(ll x, int y) {
ll ret = 0, p = x;
for (int i=1; i<=y; ++i) {
ret = ret + p;
p *= x;
if (ret > (ll)1e12) return ret;
}
return ret;
} ll bsearch(ll l, ll r, int m, ll ans) {
while (l <= r) {
ll mid = (l + r) >> 1;
ll sum = cal (mid, m);
if (sum == ans) return mid;
else if (sum < ans) l = mid + 1;
else r = mid - 1;
}
return 0;
} int main(void) {
while (scanf ("%lld", &n) == 1) {
r = 1; k = n - 1; ll kk;
for (int i=2; i<=40; ++i) {
kk = bsearch (2, 1e6, i, n);
if (kk == 0) continue;
if (1ll * i * kk < r * k) {
r = i; k = kk;
}
}
for (int i=2; i<=40; ++i) {
kk = bsearch (2, 1e6, i, n - 1);
if (kk == 0) continue;
if (1ll * i * kk < r * k) {
r = i; k = kk;
}
}
printf ("%lld %lld\n", r, k);
} return 0;
}
最新文章
- mysql数据库史上最详细起步教程(1)
- HttpResponse的使用方法
- 批处理——服务器的web文件备份
- must implement the inherited abstract method
- css\html布局及部分知识小分享~~~
- 2016年10月12日 星期三 --出埃及记 Exodus 18:23
- iOS字符串拆分
- Java与.net的区别delegate和event
- debug 输出 以及宏定义--备
- ORACLE控制文件一致性【weber出品】
- 2014第2周四部署环境&;买火车票
- CSS左中右布局,规范案例
- HTML基金会2----联系,像, 第,对齐
- 《Windows驱动开发技术详解》之HelloDDK
- MJRefresh
- POWERSHELL将域中的计算机移动到指定OU
- C++11获取线程的返回值
- Ubuntu14.04安装 HP DeskJet GT 5820 打印机的方法
- c++沉思录 学习笔记 第六章 句柄(引用计数指针雏形?)
- 调用redis的时候二维码不断刷新的排查