首页 > 代码库 > hdu 4430 Yukari's Birthday 枚举+二分
hdu 4430 Yukari's Birthday 枚举+二分
注意会超long long
开i次根号方法，te=(ll)pow(n,1.0/i);
Yukari‘s Birthday
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3262 Accepted Submission(s): 695
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
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<iostream> 7 #define maxi(a,b) (a)>(b)?(a):(b) 8 #define mini(a,b) (a)<(b)?(a):(b) 9 #define N 1000005 10 #define mod 10000 11 #define ll long long 12 13 using namespace std; 14 15 ll n; 16 ll ans; 17 ll r,k; 18 ll rr,kk; 19 20 void ini() 21 { 22 ans=n-1; 23 r=1; 24 k=n-1; 25 } 26 27 void cal3(ll x) 28 { 29 ll te,d; 30 te=1+4*x; 31 d=sqrt(te); 32 if(d*d==te){ 33 kk=(d-1); 34 if(kk%2==0){ 35 kk/=2; 36 if(kk*2<ans){ 37 ans=kk*2; 38 k=kk;r=2; 39 } 40 } 41 } 42 } 43 44 ll cal(ll a,ll cnt) 45 { 46 ll re=1; 47 while(cnt) 48 { 49 if(cnt&1){ 50 re=(re*a); 51 cnt--; 52 } 53 cnt/=2; 54 a=a*a; 55 } 56 return re; 57 } 58 59 int cal2(ll a,ll en,ll now) 60 { 61 ll i; 62 for(i=en;i>=1;i--){ 63 now+=cal(a,i); 64 if(now>n) return 0; 65 } 66 if(now<n-1) return 2; 67 if(now==n-1 || now==n){ 68 if(a*(en+1)<ans){ 69 ans=a*(en+1); 70 r=en+1; 71 k=a; 72 } 73 else{ 74 if(a*(en+1)==ans && (en+1)<r){ 75 r=en+1; 76 k=a; 77 } 78 } 79 } 80 return 2; 81 } 82 83 void solve() 84 { 85 ll te,temp; 86 cal3(n); 87 cal3(n-1); 88 ll i; 89 for(i=3;i<=45;i++){ 90 //temp=cal(2ll,i); 91 //if(temp>n) break; 92 te=(ll)pow(n,1.0/i); 93 for(kk=te;kk>=2;kk--){ 94 temp=cal(kk,i); 95 if(temp>n) continue; 96 if(cal2(kk,i-1,temp)==2){ 97 break; 98 } 99 }100 }101 }102 103 void out()104 {105 printf("%I64d %I64d\n",r,k);106 }107 108 int main()109 {110 //freopen("data.in","r",stdin);111 //scanf("%d",&T);112 // while(T--)113 while(scanf("%I64d",&n)!=EOF)114 {115 ini();116 solve();117 out();118 }119 return 0;120 }
hdu 4430 Yukari's Birthday 枚举+二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。