西行寺幽幽子
时间限制: 1 Sec内存限制:128 MB题目描述
在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了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
高精度除法，ans的数据范围有优势 ，用二分
#include<iostream>#include<cstring>#include<cmath>#include<cstdio>#include<cstdlib>#include<iomanip>#include<algorithm>#define ll long long#define inf 1000000000using namespace std;int lm,ln,lt,ans;ll m[50005],n[50005];ll t[50005];char ch[50005];bool judge(ll x){memset(t,0,sizeof(t));for(int i=1;i<=ln;i++)t[i]=n[i]*x;lt=ln;for(int i=1;i<=lt;i++){if(t[i]>=10)lt=max(lt,i+1);t[i+1]+=t[i]/10;t[i]%=10;}//cout<<lm<<" "<<lt<<endl;if(lt>lm)return 0;else if(lt<lm)return 1;else {for(int i=lt;i;i--)if(t[i]>m[i])return 0;else if(t[i]<m[i])return 1;return 1;}}int main(){scanf("%s",ch+1);lm=strlen(ch+1);for(int i=1;i<=lm;i++)m[i]=ch[lm-i+1]-'0';scanf("%s",ch+1);ln=strlen(ch+1);for(int i=1;i<=ln;i++)n[i]=ch[ln-i+1]-'0';ll l=0,r=2000000000;while(l<=r){ll mid=(l+r)>>1;if(judge(mid))ans=mid,l=mid+1;else r=mid-1;//cout<<mid<<endl;}printf("%d",ans);return 0;}
如果觉得《noip模拟赛 西行寺幽幽子 高精度除法》对你有帮助，请点赞、收藏，并留下你的观点哦！
