题意：有个人过生日在蛋糕上插蜡烛，一圈一圈的插成同心圆，要求每一圈从里到外正好依次插k的i（1~r）次幂个蜡烛，最中间圆心可插可不插，给一个n（18~1w亿）,输出k和r。并且要求k*r尽可能小，同时r尽可能小。数据一共1w组左右。

思路：看到有1w组n，并且n是10的12次方，那明显要用2分才能做了。题目时间给的很充足，所以先打个表。把小于1w亿的k的r次幂都打到表里（1次幂就不要打了，会超内存）注意底数

只要取到10的6次幂就行，最后打出来的表大小101w出头，然后有个很重要的工作是去重（因为这个WA了几次）把相邻的值一样的结点比较一下，取最优值留下。然后就2分找就行了，找到一个点注意再看看他前面的那个值能不能+1等于n，再比较一下。这样除了打表，时间复杂度是T*log(100w)总共20w，基本可以忽略了。

Yukari's Birthday

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4181    Accepted Submission(s): 946

Problem Description

Today is Yukari's n-th birthday. Ran and Chen hold a celebration party for her. Now comes the most important part, birthday cake! But it's a big challenge for them to place n candles on the top of the cake. As Yukari has lived for such a long long time, though she herself insists that she is a 17-year-old girl.
To make the birthday cake look more beautiful, Ran and Chen decide to place them like r ≥ 1 concentric circles. They place ki candles equidistantly on the i-th circle, where k ≥ 2, 1 ≤ i ≤ r. And it's optional to place at most one candle at the center of the cake. In case that there are a lot of different pairs of r and k satisfying these restrictions, they want to minimize r × k. If there is still a tie, minimize r.

Input

There are about 10,000 test cases. Process to the end of file.
Each test consists of only an integer 18 ≤ n ≤ 1012.

Output

For each test case, output r and k.


Sample Input

18
111
1111


Sample Output

1 17
2 10
3 10


Source

2012 Asia ChangChun Regional Contest

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;LL n;struct node{long long r,k;long long v;friend bool operator<(const node &a,const node &b){return a.v<b.v;}
};node A[1020000];bool cmp(const node &a,const node &b){return a.v<b.v;}node cmpnode(node a,node b){if(a.r*a.k<b.r*b.k)return a;else if(a.r*a.k==b.r*b.k){if(a.r<b.r)return a;}return b;
}int main(){int num=0;memset(A,0,sizeof(A));for(long long i=2;i<1000000;i++){long long sum=i;long long t=1;for(long long j=i*i;sum<=1000000000000;j*=i){t++;sum+=j;if(sum<=1000000000000){//&&(t*i<sum-1)这个写不写都行，不存在r*k<n-1的情况A[num].r=t;A[num].k=i;A[num].v=sum;num++;//                A[num].r=t;
//                A[num].k=i;
//                A[num].v=sum+1;
//                num++;}}}
//    cout<<num<<endl;sort(A,A+num,cmp);
//    cout<<num<<endl;
//    for(int i=0;i<200;i++){
//        printf("%lld\n",A[i].v);
//    }//去重，同等数字只保留最优值int newnum=0;for(int i=0;i<num;i++){
//        if(A[i].v==A[i+1].v&&A[i+1].v==A[i+2].v)cout<<"fuck";
//通过此句判断出不存在3连等的情况if(A[i].v==A[i+1].v){
//            cout<<A[i].v<<"fuck"<<endl;A[newnum++]=cmpnode(A[i],A[i+1]);i++;}else A[newnum++]=A[i];}//  cout<<newnum<<endl;node f;node c;f.v=0;node *o=lower_bound(A,A+num,f);while(scanf("%lld",&n)!=EOF){c.v=n;//node l=*lower_bound(A,A+num,c);int l=lower_bound(A,A+num,c)-o;int r=upper_bound(A,A+num,c)-o;
//        cout<<l<<r<<endl;
//        node mif(l==r){if(A[l-1].v+1==n){if(A[l-1].r*A[l-1].k<n-1){printf("%lld %lld\n",A[l-1].r,A[l-1].k);continue;}}}else{node m=A[l];if(A[l-1].v+1==n){if(A[l-1].r*A[l-1].k<n-1){m=cmpnode(A[l-1],m);}}if(m.r*m.k<n-1){printf("%lld %lld\n",m.r,m.k);continue;}}printf("1 %lld\n",n-1);}return 0;
}