眾所周知，琪露諾(チルノ，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]);
}
}
我沒有時間詳細看你的代碼，這裡給出這類題的解題思路。
1）遍歷
從最小的值到最大的值遍歷，將其中含1的個數加起來，這樣就得到答案。但這樣最大的缺點是效率不高，因為復雜度O（N*lgN). 另外，f(N,M) = f(1,M)-f(1,N-1).
2) 發現規律
假設求f(1,N).
f(1,125) = 個位數出現9個數 + 十位數出現9的個數 + 百位出現的9的個數。
