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

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





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;
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