BZOJ1263: [SCOI2006]整数划分【高精度】

dzy posted @ 2013年6月07日 16:53 in BZOJ with tags BZOJ 高精度 , 2401 阅读

果然是3越多越好、、滚回去学小学奥数算了、、、

然后就是高精度了、、比较脑残选择了手写、、更加脑残的选择了压位和快速幂、、然后跑的还行、、

代码越写越短了、、不过还有更短的比不过、、呵呵、、、

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Hugeint{
    ll len,num[10000];  Hugeint(){  len=1ll;  memset(num,0,sizeof(num));}
}An;ll n,two,thr,p[]={1,10,100,1000};
Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(ll i=1;i<=a.len;i++) for(ll j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(ll i=1;i<c.len;i++)  if(c.num[i]>9999)  c.num[i+1]+=c.num[i]/10000,  c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,  c.num[c.len]+=c.num[c.len-1]/10000,   c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1)  c.len--;   return c;
}Hugeint pow(ll b,ll p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}inline int len(int x){
    int r=0; while(x)r++,x/=10; return r;
}void print(Hugeint a){
    if(a.len<=25){ printf("%lld",a.num[a.len]); for(ll i=a.len-1;i;i--)printf("%04lld",a.num[i]); return;} 
    printf("%lld",a.num[a.len]);    for(ll i=a.len-1;i>=a.len-24;i--)printf("%04lld",a.num[i]);
    if(len(a.num[a.len])<4) printf("%lld\n",a.num[a.len-25]/p[len(a.num[a.len])]);
}int main(){
    scanf("%lld",&n); two=0,thr=n/3;  if(n%3)two=2/(n%3),thr=(n-4/(n%3))/3; An=Mul(pow(2,two),pow(3,thr));
    printf("%lld\n",(An.len-1<<2)+len(An.num[An.len])); print(An);  return 0;
}
Avatar_small
Emma 说:
2023年1月27日 02:23

It's a great reminder that the more we challenge ourselves, the better prepared we are for anything. The challenge of this BZOJ1263: [SCOI2006] Integer division [high precision] is a engagement rings perfect example of that. By choosing handwriting for comparison and fast power for the more stupid, you were able to solve the problem efficiently. Not to mention, this code is written concisely, proving that practice makes perfect.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter