Description
给定一个十进制正整数N,写下从1开始，到N的所有整数，然后统计一下其中出现的所有的“1”的个数。例如： N=2,写下1 ，2。这样只出现了1个“1”. N=12,我们会写下1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，10 ，11 ，12。这样，1的个数是5。那么，给定已知的正整数N，你是否能给出N以内所有正整数中出现1的总数。
Input
首先输入一个正整数T（1<=T<=1000），表示一共有T组测试样例，接下来有T行输入，每行输入一个正整数N（1<=N<2147483647）。
Output
针对每个测试用例，输出N以内所有正整数出现1的总数，相邻的总数结果用一个回车分隔。
Sample Input
4
1
11
15
99
Sample Output
1
4
8
20

HINT
结果值可能超出基本整形表示范围，需要用到64位的整型。
C语言中，64位的整型有两种：
第一种：用于gcc编译环境下的long long 型，其输入输出格式控制符为%lld。“lld”意为long long decimal。例如：
long long a;
scanf("%lld",&a);
printf("%lld",a);
第二种：用于Mircrosoft Visual C++编译环境的__int64。“__”为双下划线，其 输入输出格式控制符为%I64d, 其中“I64d”表示，Integer 64 decimal。例如：
__int64 a;
scanf("%I64d",&a);
printf("%I64d",a);

这样的话耗时比较多！运行结果是对的，但是会超时，有没有可以改进的方案！缩小时间复杂度！

#include<stdio.h>   
int main()
{
    int n,k,i,r,count,j;
    long m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        count=0;
        scanf("%ld",&m);
        for(j=1;j<=m;j++)
        {
             k=j;
             while(k>0)
             {
                 r=k%10;
                 if(r==1)
                     count++;
                 k=k/10;
             }
        }
        printf("%d\n",count);
    }
    return 0;
}

我学了数据结构责骂感觉用不上啊？？？有什么提高程序运行效率的没！！我那个代码运行严重超时啊！求改进！求算法！

不满你说，感觉你涉及到的东西都怎么这么难啊！！很难看懂的！呵呵，不知道是不是缺少注释语句 啊？？嘿嘿

哈哈，我体会体会哦！！！有点长！重在学习！

想法很好！！但是.....哎！！还是算了吧