西行寺幽幽子

· · 个人记录

题目

题目描述

在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡 灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人 间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了 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

思路一

直接模拟
O(N^2)

code(还没调出来)

#include<bits/stdc++.h>
using namespace std;
const int N=21010;
char s1[N],s2[N];
int a[N],b[N],c[N],d[N];
int la,lb,lc,ld,sum;
bool BigJudge(){
    if(lc<lb)return false;
    if(lc>lb)return true;
    for(int i=lb;i>=1;i--){
        if(c[i]>b[i])return true;
        if(c[i]<b[i])return false;
    }
    return true;
}
void AddD(int key){
    ld=lb;
    for(int i=1;i<=lb;i++)
        d[i]=b[i]*key;
    d[ld+1]=0;
    for(int i=1;i<=lb;i++){
        d[i+1]+=d[i]/10;
        d[i]=d[i]%10;
    }
    if(d[ld+1])ld++;
    return;
}
bool TimesJudge(int key){
    AddD(key); 
    if(lc<ld)return false;
    if(lc>ld)return true;
    for(int i=ld;i>=1;i--){
        if(c[i]>d[i])return true;
        if(c[i]<d[i])return false;
    }
    return true;
}
void Work(int key){
    AddD(key);
    int Nlc=0;
    for(int i=1;i<=lc;i++){
        c[i]-=d[i];
        if(c[i-1]<0)c[i]--,c[i-1]+=10;
        if(c[i]>0)Nlc=i;
    }
    lc=Nlc;
    return;
} 
void AddC(){
    lc++;
    int last=0,rcd=0;
    for(int i=1;i<=lc;i++){
        rcd=c[i];
        c[i]=last;
        last=rcd;
    } 
    return;
}
int main(){
    //freopen("spring.in","r",stdin);
    //freopen("spring.out","w",stdout);
    cin>>s1+1;
    cin>>s2+1;
    la=strlen(s1+1);
    lb=strlen(s2+1);
    for(int i=1;i<=la;i++)
        a[i]=s1[la-i+1]-'0';
    for(int i=1;i<=lb;i++)
        b[i]=s2[lb-i+1]-'0';
    for(int i=la;i>=1;i--){
        AddC();
        c[1]=a[i];
        if(BigJudge()){
            int l=1,r=9,ans=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(TimesJudge(mid)){
                    ans=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            sum*=10;
            sum+=ans;
            Work(ans);
        }
        else{
            sum*=10;
            if(lc==1 && c[1]==0)
            lc--;
        }
    }
    printf("%d",sum);
    return 0;
}

思路二

O(n log n)
由于ans范围很小
可以二分枚举ans
乘回去验证
单精对高精

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10; 
char a[N],b[N];
long long ans,s1[N],s2[N],c[N],la,lb,lc;
void work(long long key){
    for(int i=lc;i>=1;i--)c[i]=0;
    lc=lb;
    for(int i=1;i<=lb;i++)
        c[i]=key*s2[i];
    for(int i=1;i<lc;i++){
        c[i+1]+=c[i]/10;
        c[i]=c[i]%10;
    } 
    while(1){
        if(c[lc]>=10){
            c[lc+1]=c[lc]/10;
            c[lc]=c[lc]%10;
        }
        else break;
        lc++;
    }
    return;
}
bool check(){
    if(lc<la)return true;
    if(lc>la)return false;
    for(int i=1;i<=lc;i++){
        if(c[i]<s1[i])return true;
        if(c[i]>s1[i])return false;
    }
    return true;
}
int main(){
    cin>>a+1>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for(int i=la;i>=1;i--)
        s1[i]=a[la-i+1]-'0';
    for(int i=lb;i>=1;i--)
        s2[i]=b[lb-i+1]-'0';
    long long l=0,r=2e9;
    while(l<=r){
        long long mid=(l+r)>>1;
        work(mid);
        if(check())ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}