首页 > 代码库 > zoj 3665 数论 二分 两个参数
zoj 3665 数论 二分 两个参数
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4888
两个参数的题,处理方法:枚举小的那个参数,然后二分大的参数
想到二分了,然后两个参数就不会了 然后暴力了下,但是其实K可以很大 所以时间不够
自己写的二分枚举+快速幂程序WA了很久。。。。没明白哪里错了 参考了别人的。。。
//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-8; const double pi = acos(-1.0); const int INF = 100000000; ll n,ansr,ansk; void test(ll d, ll up, int r) { ll sum; while(d<up) { ll mid=(d+up)/2; sum=0; ll know=1;//k^i int flag=0; for(int i=1;i<=r;i++) { know*=mid; sum+=know; if(sum>1000000000000LL || sum<0 ) { flag=1; break; } } if(flag) { up=mid; continue; } if(sum>n)up=mid; else d=mid+1; if(sum+1 == n || sum==n) { if(mid*r < ansr*ansk) ansr=r,ansk=mid; break; } } } int main() { IN("zoj3665.txt"); while(~scanf("%lld",&n)) { ansr=1; ansk=n-1;// for(int i=2;i<=64;i++) test(1ll,1000000,i); printf("%lld %lld\n",ansr,ansk); } return 0; }
zoj 3665 数论 二分 两个参数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。