题意:把n只蜡烛插在蛋糕上,中间可以插1只蜡烛,也可以不插,,外面r层,每层为k^i只。k>1 问rk取何值时,可以把n只蜡烛都插上,。如果多种方法,取r最小的。。
思路:把r>3,r=2,r=1;分开考虑;
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <queue> #include <stack> #include <map> using namespace std; #define LL long long LL X = 1000000000000ll; struct nod{ int r,k; } re[12000]; int cnt; LL oor0(int r,int k) { LL ret=0; for(int i=1;i<=r;i++) { ret+=pow(k,i); if(ret>X) return -1; } return ret; } map<LL,int> mp; void init() { for(int i=3;i<64;i++) { for(int j=2;j<10009;j++) { LL t = oor0(i,j); if(t<=0) break; re[cnt].r = i,re[cnt].k = j; mp[t] = cnt; cnt++; t++; } } } int main() { freopen("in.txt","r",stdin); init(); LL a; LL x,y; while(cin>>a) { if(mp.find(a)!=mp.end()) { int k = mp[a]; x = re[k].r,y=re[k].k; } else if(mp.find(a-1)!=mp.end()) { int k = mp[a-1]; x = re[k].r,y=re[k].k; }else{ LL k = (LL)sqrt(a);//cout<<k<<endl; if(k*(k+1)==a||k*(k+1)==a-1){ x = 2,y =k; }else{ x = 1,y=a-1; } } cout<<x<<" "<<y<<endl; } return 0; }