zoj 3665 Yukari's Birthday(列挙+二分)
2586 ワード
Yukari's Birthday
Time Limit: 2 Seconds
Memory Limit: 32768 KB
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
Sample Output
この問題は周試合の時にやったのですが、私は試合後自分で何時間も書いたので、能力がだめですね.いつも間違いばかりしています.
この問題はべき乗を計算する時システムのpow関数を呼び出すほうがいいです.アルゴリズムのようにpowを呼び出すのは私の何倍も速いです.これも後で気づいたのですが、私がどんなに最適化しても他の人よりずっと遅いからです.
このテーマの中で言うのはもし等しいr*kがrの最小を取るならば、私はr*kの表現式を書いて、それに対して導いた後にそれがkについて単調に増加していることを発見して、私は直接rの最大の時から、このように最初に見つけたkは最小で、いったん見つけたらすぐに退出することができて、Aで.あのようないくつかのr*kが等しい情況があるかどうかについて私も証明することができません
Time Limit: 2 Seconds
Memory Limit: 32768 KB
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
この問題は周試合の時にやったのですが、私は試合後自分で何時間も書いたので、能力がだめですね.いつも間違いばかりしています.
この問題はべき乗を計算する時システムのpow関数を呼び出すほうがいいです.アルゴリズムのようにpowを呼び出すのは私の何倍も速いです.これも後で気づいたのですが、私がどんなに最適化しても他の人よりずっと遅いからです.
このテーマの中で言うのはもし等しいr*kがrの最小を取るならば、私はr*kの表現式を書いて、それに対して導いた後にそれがkについて単調に増加していることを発見して、私は直接rの最大の時から、このように最初に見つけたkは最小で、いったん見つけたらすぐに退出することができて、Aで.あのようないくつかのr*kが等しい情況があるかどうかについて私も証明することができません
#include<stdio.h>
#include<math.h>
double logn;
long long n;
long long fun(long long k,int i)
{
int j;
long long s=1,sum=0;
for(j=0;j<i;j++)
{
if(s>n/k)
return n+1;
s*=k;
sum+=s;
if(sum>n)
return n+1;
}
return sum;
}
int main()
{
int i,j,r,num;
long long minx,mink,minr,min,max,mid,ki,temp;
while(scanf("%lld",&n)!=EOF)
{
logn=log((double)n);
num=log((double)n)/log(2.0);
minx=n;
for(i=num;i>=1;i--)// r
{
min=1;
max=n;
while(min<=max)
{
mid=(min+max)/2;
temp=fun(mid,i);
if(temp>n)
max=mid-1;
else if(temp<(n-1))
min=mid+1;
if(temp==n||temp==n-1)
{
if(minx>i*mid)
{
minx=i*mid;
mink=mid;
minr=i;
}
break;
}
}
}
printf("%lld %lld
",minr,mink);
}
return 0;
}