众所周知,琪露诺(チルノ,Cirno)是幻想郷 (げんそうきょう)中首屈一指的天才,可以说⑨就是她的代名词。
然而如今,她遇到了一个和⑨有关的难题。你能帮助她么?
题目是这样的,给出两个数 a 和 b (0 <= a <= b <= 10^10000),求 a 到 b 之间(包括a和b)的数字中,有多少个数字是包含9的(例如 19,910 等都是包含9的数字)。
输入
第一行为一个数字 T (0 < T <= 100) 表示数据组数。
之后的 T 行,每行包含两个数 a 和 b (0 <= a <= b <= 10^10000)。
输出
对每组数据输入,输出一个数字,表示 a 到 b 之间的数字中(包括a和b),有多少个数字是包含9的。(注意:答案可能很大)
测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1 以文本方式显示
1. 1↵
2. 0 9↵ 1. 1↵
这是我的作法不对啊
#include"stdio.h"
int mul(int a,int d,int l)
{int i;
for (i = 0; i < l; i++)
{
a[i] = a[i] * d;
}
for (i = 0; i < l; i++)
{
a[i + 1] += a[i] / 1000000;
a[i] = a[i]%1000000;
}
if(a[l]!=0)
l++;
return l;
}
int plus(int *x, int *y,int l)
{
int i;
for (i = 0; i < l; i++)
{
x[i] += y[i];
if (x[i] >= 1000000)
{
x[i + 1]++;
x[i] -= 1000000;
}
}
if(x[l]!=0)
l++;
return l;
}
int minus(int *x, int *y, int *z,int l)
{
int i;
for (i = 0; i
{
z[i] += x[i] - y[i];
if (z[i]
{
z[i + 1]--;
z[i] += 1000000;
}
}
while(l>0&&z[l-1]==0)
{
l--;
}
return l;
}
main()
{
int a[100]={0},b[100]={0},c[100]={0},d[100]={0};
int e[100]={0},f[100]={0},g[100]={0},h[100]={0};
int flag=1,pda9=1,pdb9=1,i,j,T;
int lena=1,lenc=1,lend=1,lene=1,lenf=1,leng=1,lenh=1;
char ch;
scanf("%d\n",&T);/输入的行数*/
for(i=0;i<T;i++)
{
for(;;)/*如果遇到\n,退出循环*/
{ ch=getchar();
if(ch=='\n') break;
if(ch==' ') { flag=0;continue;}/*遇到空格表明该计算小的数含9个数了*/
if(flag==1)
{ b[0]=ch-'0';
lenc=mul(c,10,lenc);lenc=plus(c,b,lenc);/*先乘以10再加读入的数,lenc是所得数的位数*/
if(ch=='9') pda9=0;/*接下来计算含9的个数,做标记分两种情况*/
if(pda9==0) lena=mul(a,9,lena);
if(pda9==1) {lena=mul(a,9,lena);lena=plus(a,b,lena);}
}
if(flag==0) /*计算大的数含9个数*/
{
b[0]=ch-'0'; /*将b转换为整形,只有一位,后面要被加*/
lend=mul(d,10,lend);lend=plus(d,b,lend);/*lend是所得位数*/
if(ch=='9') pdb9=0;/*同上*/
if(pdb9==0) lene=mul(e,9,lene);
if(pdb9==1){lene=mul(e,9,lene);plus(e,b,lene);}
}
}
lenf=minus(c,a,f,lenc); /*f是小的数里面含的9的个数,f=c-a*/
leng=minus(d,e,g,lend);/*g是大的数里面含的9的个数,g=d-e*/
if(pdb9==0) {b[0]=1;leng=plus(g,b,leng);} /*遇到9,大的数里面含的9个数要加1*/
lenh=minus(g,f,h,leng);
for(j=lenh-1;j>=0;j++)
printf("%d",h[j]);
}
}