HDU 4430 Yukari's Birthday

系统管理员 2022-07-12 16:15 96阅读 0赞

<table style="font-family:&quot;Times New Roman&quot;; word-wrap:break-word"> 
 <tbody> 
  <tr> 
   <td align="center"> <h1 style="color:rgb(26,92,200)">Yukari's Birthday</h1> <strong><span style="font-family:Arial; color:green">Time Limit: 12000/6000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others)<br> Total Submission(s): 5449&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 1309<br> </span></strong><br> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Problem Description 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      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. 
     <br> To make the birthday cake look more beautiful, Ran and Chen decide to place them like r ≥ 1 concentric circles. They place k 
     <sup>i</sup>&nbsp;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. 
     <br> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      There are about 10,000 test cases. Process to the end of file. 
     <br> Each test consists of only an integer 18 ≤ n ≤ 10 
     <sup>12</sup>. 
     <br> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      For each test case, output r and k. 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">
      
       
      <div style="font-family:&quot;Courier New&quot;,Courier,monospace">
       
        
       18
111
1111
      
       
      </div></pre> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">
      
       
      <div style="font-family:&quot;Courier New&quot;,Courier,monospace">
       
        
       1 17
2 10
3 10
      
       
      </div>
      
       
      <div>

</div></pre> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    #define ll __int64
    
    ll n;
    
    ll bin(ll s)
    {
        ll l = 2,r = n,mid,i;
        while(l<=r)
        {
            mid = (l+r)/2;
            ll sum = 1,ans = 0;;
            for(i = 1; i<=s; 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()
    {
        ll s,k,l,r,mid,i;
        while(~scanf("%I64d",&n))
        {
            l = 1,r = n-1;
            for(i = 2; i<=45; i++)
            {
                k = bin(i);
                if(k!=-1 && i*k<l*r)
                {
                    l = i,r = k;
                }
            }
            printf("%I64d %I64d\n",l,r);
        }
    
        return 0;
    }