首页 > 代码库 > HDU - 4430 - Yukari's Birthday
HDU - 4430 - Yukari's Birthday
题目链接:https://vjudge.net/problem/HDU-4430
题目大意:
给出一个n,求出一个r和k,使得首项是k,公比是k的前0~r项和为n,且r*k尽量小。
题目分析:
首先利用等比数列的前n项和公式大概估算出r的大小范围大概最多为45左右。
此时可以枚举r,二分k,求得符合题意的r和k。
注意在二分的过程中可能会溢出,要进行预处理。
注:一开始n开成了int ,WA了一晚上,有毒。
给出代码:
#include <cstdio> #include <iostream> #include <string> #include <set> #include <cmath> #include <algorithm> #include <cstring> #include <vector> using namespace std; long long int n; long long int find(long long int x) { long long int l=2,r=n,mid,i; while(l<=r) { //cout<<mid<<endl; mid=(l+r)/2; long long int sum=1; long long int ans=0; for(i=1; i<=x; i++) { if(n/sum<mid) { ans=n+1; break; } sum*=mid;; ans+=sum; if(ans>n) break; } if(ans==n||ans==n-1) return mid; else { if(ans<n-1) l=mid+1; else r=mid-1; } } return -1; } int main() { //cin>>n; while(cin>>n) { //long long int minn=n-1; /* if(n==1) { cout<<0<<" "<<1<<endl; continue; }*/ long long int r=1,k=n-1,i; for(i=2; i<=45; i++) { long long int t=find(i); // cout<<t<<" "<<i<<endl; if(t==-1) continue; if(t*i<k*r) { // minn=t*i; r=i; k=t; } } cout<<r<<" "<<k<<endl; } return 0; }
HDU - 4430 - Yukari's Birthday
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。