Guest User

Get there faster

a guest
Jan 29th, 2012
434
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. using namespace std;
  5.  
  6. /// Compiles just fine (TM) with G++ 4.7 in -std=c++0x mode
  7.  
  8. typedef unsigned __int128 llu;
  9. typedef long long unsigned ull;
  10.  
  11. llu bb(llu x){
  12.   llu best=x;
  13.   if (x==1) return 1;
  14.   llu k=1,kb=2;
  15.   while (kb<=x){
  16.     llu l=k,r=(__int128)-1; r>>=(__int128)2;
  17.     while (l<r){
  18.       llu n=(l>>(__int128)1)+(r>>(__int128)1)+(l&r&1);
  19.       llu res=1;
  20.       for (llu m=1; m<=k and res<=x; m++)
  21.         res*=(m+n-k),res/=m;
  22.       if (res==x){
  23.         best=min(best,n);
  24.         break;
  25.       }
  26.       if (res<x) l=n+1;
  27.       else r=n;
  28.     }
  29.     ++k;kb*=(k*2-1)*(k*2),kb/=k*k;
  30.   }
  31.   return best;
  32. }
  33.  
  34. int main(){
  35.   if(freopen("checkpoint.in","r",stdin));
  36.   if(freopen("checkpoint.out","w",stdout));
  37.  
  38.   int tsts; if(scanf("%d",&tsts)); for (int tst=1; tst<=tsts; tst++){
  39.     llu ways; ull proxy; if(scanf("%llu",&proxy)); ways=proxy;
  40.     llu best=-1;
  41.     for (llu i=1; i*i<=ways; i++)
  42.       if (ways%i==0)
  43.         best=min(best,bb(i)+bb(ways/i));
  44.     printf("Case #%d: %llu\n",tst,(ull)best);
  45.   }
  46. }
RAW Paste Data