【codevs 1331】西行寺幽幽子

点击就送屠龙宝刀

题目描述

在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了M个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要N个单位的春度。现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。

输入描述

第1行：一个正整数M

第2行：一个正整数N

N,M的位数不超过L，L的范围在题目后面给出

输出描述

第1行：一个整数ans，表示能开出花的朵数

样例输入

7386175812471

样例输出

5922

数据范围

对于60%的数据：L <= 2,000且ans <= 2,000

对于100%的数据：L <= 20,000且ans <= 2,000,000,000

高精除，没了

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int size=20010;const int BASE=(int)1e9;const int WIDTH=9;typedef long long LL;struct bign{int len,num[size];bign(){memset(num,0,sizeof(num)); len=1;}bign(LL x){memset(num,0,sizeof(num)); len=0;do{num[++len]=x%BASE;x/=BASE;}while(x);}};void scanf(bign &ans){string in;cin>>in;int l=in.length();ans.len=(l-1)/WIDTH+1;for(int i=0;i<ans.len;i++){int e=l-i*WIDTH;int s=max(0,e-WIDTH);sscanf(in.substr(s,e-s).c_str(),"%d",&ans.num[i+1]);}}void printf(const bign &ans){printf("%d",ans.num[ans.len]);for(int i=ans.len-1;i>=1;i--){printf("%09d",ans.num[i]); }}bool operator <(const bign &a,const bign &b){if(a.len!=b.len) return a.len<b.len;for(int i=a.len;i>=1;i--)if(a.num[i]!=b.num[i]) return a.num[i]<b.num[i];return false;}bign operator +(const bign &a,const bign &b){bign ans;int i=1,x=0;while(i<=a.len||i<=b.len){x=a.num[i]+b.num[i]+x;ans.num[i++]=x%BASE;x/=BASE;}ans.num[i]=x;ans.len=i;while(ans.len>1&&ans.num[ans.len]==0) ans.len--;return ans;}bign operator -(const bign &a,const bign &b){bign ans;ans.len=a.len;for(int i=1,x=0;i<=a.len;i++){x=BASE+a.num[i]-b.num[i]+x;ans.num[i]=x%BASE;x=x/BASE-1;}while(ans.len>1&&ans.num[ans.len]==0) ans.len--;return ans;}bign operator *(const bign &a,const bign &b){bign ans;ans.len=a.len+b.len;for(int i=1;i<=a.len;i++){LL x=0;for(int j=1;j<=b.len;j++){x+=ans.num[i+j-1]+(LL)a.num[i]*(LL)b.num[j];ans.num[i+j-1]=x%BASE;x/=BASE;}ans.num[i+b.len]=x;}while(ans.len>1&&ans.num[ans.len]==0) ans.len--;return ans; }bool smaller(const bign &a,const bign &b,int d){if(a.len+d!=b.len) return a.len+d<b.len;for(int i=a.len;i>=1;i--)if(a.num[i]!=b.num[i+d]) return a.num[i]<b.num[i+d];return true;}void jian(bign &a,const bign &b,int d){for(int i=1,x=0;i<=a.len-d;i++){x=BASE+a.num[i+d]-b.num[i]+x;a.num[i+d]=x%BASE;x=x/BASE-1;}while(a.len>1&&a.num[a.len]==0) a.len--;}bign operator /(const bign &a,const bign &b){bign ans;ans.len=max(1,a.len-b.len+1);bign mid[32],num=a;mid[0]=b;for(int i=1;i<=30;i++) mid[i]=mid[i-1]*2;for(int i=a.len-b.len;i>=0;i--){int tmp=1<<30;for(int j=30;j>=0;j--){if(smaller(mid[j],num,i)){jian(num,mid[j],i);ans.num[i+1]+=tmp;}tmp>>=1;}}while(ans.len>1&&ans.num[ans.len]==0) ans.len--;return ans;}bign operator %(const bign &a,const bign &b){bign ans;ans.len=max(1,a.len-b.len+1);bign mid[32],num=a;mid[0]=b;for(int i=1;i<=30;i++) mid[i]=mid[i-1]*2;for(int i=a.len-b.len;i>=0;i--){int tmp=1<<30;for(int j=30;j>=0;j--){if(smaller(mid[j],num,i)){jian(num,mid[j],i);ans.num[i+1]+=tmp;}tmp>>=1;}}return num;}int main(){bign a,b;scanf(a);scanf(b);printf(a/b);return 0;}

如果觉得《【codevs 1331】西行寺幽幽子》对你有帮助，请点赞、收藏，并留下你的观点哦！