处女座和小姐姐（三）

https://ac.nowcoder.com/acm/contest/329/G

题解：

std

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SET0(x) memset(x,0,sizeof(x));
#define MAXN 10010
#define DMAX 100000000
char l[MAXN],r[MAXN];
int max(int a,int b){return a>b?a:b;}
int ninepow[MAXN][1300]={0};
void out(int *src){
    for(int i=src[0];i>=1;i--){
        if(i!=src[0])
            printf("%08d",src[i]);
        else
            printf("%d",src[i]);
    }
    printf("\n");
}
void mul(int *src,int *dec,int d){
    int res=0;
    for(int i=1;i<=src[0];i++){
        dec[i]=src[i]*d;
        dec[i]+=res;
        res=dec[i]/DMAX;
        dec[i]%=DMAX;
    }
    dec[0]=src[0];
    if(res){
        dec[++dec[0]]=res;
    }
}
 
void add(int *src1,int *src2,int *dec){
    int res=0;
    for(int i=1;i<=src1[0]||i<=src2[0];i++){
        dec[i]=src1[i]+src2[i]+res;
        res=dec[i]/DMAX;
        dec[i]=dec[i]%DMAX;
    }
    dec[0]=max(src1[0],src2[0]);
    if(res){
        dec[++dec[0]]=res;
    }
}
void sub(int *src1,int *src2,int *dec){
//    out(src1);
//    printf("-\n");
//    out(src2);
    int res=0;
    for(int i=1;i<=src1[0]||i<=src2[0];i++){
        dec[i]=src1[i]-src2[i]-res;
        if(dec[i]<0){
            res=1;
        }
        else{
            res=0;
        }
        dec[i]=(dec[i]%DMAX+DMAX)%DMAX;
//        printf("%d %d ",src1[i],src2[i]);
//        printf("%d\n",dec[i]);
    }
    dec[0]=max(src1[0],src2[0]);
    while(dec[dec[0]]==0&&dec[0]>1) {
        dec[0]--;
    }
}
 
 
 
 
void cti(char *src,int *dec){
    int len=(int)strlen(src);
    dec[0]=(len-1)/8+1;
    int cnt=8-(len-1)%8-1;
    for(int i=0;i<len;i++){
        dec[dec[0]-cnt/8]*=10;
        dec[dec[0]-cnt/8]+=src[i]-'0';
        cnt++;
    }
}
 
 
int num[1300];
int tep[1300];
int sum[1300];
int ans[3][1300];
int isl;
void solve(char *s,int *ans){
    SET0(sum);
    SET0(num);
    cti(s,num);
 
//    if(isl)printf("l:");
//    else printf("r:");
//    out(num);
 
    int seven=0;
    int len=(int)strlen(s);
    for(int i=0;i<len;i++){
        if(s[i]>'6'){
            SET0(tep);
            mul(ninepow[len-i-1],tep,s[i]-'0'-1);
            add(tep,sum,sum);
        }
        else if(s[i]=='6'){
            SET0(tep);
            mul(ninepow[len-i-1],tep,6);
            add(tep,sum,sum);
            seven=1;
            break;
        }
        else{
            SET0(tep);
            mul(ninepow[len-i-1],tep,s[i]-'0');
            add(tep,sum,sum);
        }
//        out(sum);
    }
 
    if(seven&&isl==0){
        sub(sum,ninepow[0],sum);
    }
//    printf("sum:");
//    out(sum);
//
    sub(num,sum,ans);
 
//    printf("ans:");
//    out(ans);
//    printf("\n");
}
 
int main(int argc, const char * argv[]) {
 
 
 
    ninepow[0][0]=1;
    ninepow[0][1]=1;
    for(int i=1;i<MAXN;i++)
        mul(ninepow[i-1],ninepow[i],9);
    SET0(ans);
    scanf("%s%s",l,r);
    isl=1;
    solve(l,ans[0]);
    isl=0;
    solve(r,ans[1]);
    sub(ans[1],ans[0],ans[2]);
    out(ans[2]);
    return 0;
}