「NOIP模拟赛」西行寺幽幽子
| 题目描述 | 在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了M个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要N个单位的春度。现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。 |
| 输入格式 | 第1行：一个正整数M
第2行：一个正整数N N,M的位数不超过L，L的范围在题目后面给出 |
| 输出格式 | 第1行：一个整数ans，表示能开出花的朵数 |
| 输入样例 | 73861758
12471 |
| 输出样例 | 5922 |
| 数据范围 | 对于60%的数据：L <= 2,000且ans <= 2,000
对于100%的数据：L <= 20,000且ans <= 2,000,000,000 |
高精度除法。。。
二分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int lm,ln,lt,ans; ll m[50005],n[50005]; ll t[50005]; char ch[50005]; bool jud(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; } 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() { // m/n 高精度 //freopen("spring.in","r",stdin); //freopen("spring.out","w",stdout); 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(jud(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9786897
OI 课件=>
OI 课件=>