2012年亚洲长春区域赛：K Yukari's Birthday

K - Yukari's Birthday

Time Limit:6000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

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 $\ge$ 1 concentric circles. They place kⁱcandles equidistantly on the i-th circle, where k $\ge$ 2, 1 $\le$ i $\le$ 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 x 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 $\le$ n $\le$ 10¹².

Output

For each test case, output r and k.

Sample Input

Sample Output

解题思路：利用等比数列求和公式求出n或n-1的表达式：n (或n-1) = k * ( K^r- 1) / ( k - 1) ；

可以得出k是n或n-1的一个因子，则我们可以枚举r（枚举k会超时）

解题代码：

View Code

 1 // File Name: K - Yukari's Birthday
 2 // Author: sheng
 3 // Created Time: 2013年04月18日 星期四 13时47分51秒
 4 
 5 #include <stdio.h>
 6 #include <math.h>
 7 long long a,b,n;
 8 void f(long long n)
 9 {
10     long long f,s,i,k,j;
11     for (i=2;i<=50;i++)
12     {
13         s=0;f=1;
14         k=(long long)pow(n,1.0/i);
15         for (j=1;j<=i;j++)
16         {
17             f*=k;
18             s+=f;
19             if (s==n && i*k<a*b)
20             {
21                 a=i;
22                 b=k;
23                 break;
24             }
25         }
26     }
27 }
28 int main()
29 {
30     while (~scanf("%lld",&n))
31     {
32         a=1;b=n-1;
33         f(n);
34         f(n-1);
35         printf("%lld %lld\n",a,b);
36     }
37     return 0;
38 }