Simple Addition

编程基础——函数调用

1.6：Simple Addition

题目：
输入
• 输入包含若干行。每行给出两个非负整数p和q（p≤q），这两个整数之间用一个空格隔开，p和q是32位有符号整数。输入由包含两个负整数的行结束。程序不用处理这一行。
++++输出
• 对于每行输入，输出一行，给出S(p, q)的值。

试题分析：
•例如，求S(2, 53)，将范围划分为3个区间：[2, 9]，[10, 50]和[51, 53]。
• 对于第1个区间[2, 9]，个位数之和2+3+4+……+9=44；对于第2个区间[10, 50]，个位数之(1+2+……+9)4= 454 = 180；对于第3个区间[51, 53]，个位数之和1+2+3 = 6。所以，第一轮，位数的总和为44+180+6 = 230。
• 在[10, 50]中，10, 20, 30, 40和50的个位数是0，将这些数除以10后 得1, 2, 3, 4, 5，产生新区间[1, 5]；进入第二轮，区间[1, 5]中的数只有个位数，个位数之和1+2+3+4+5=15。
• 最后，两轮结果相加，得S(2, 53)=230+15=245。

注意点：
• 利用函数求出该区间中每位数的和
•一个一个算，时间复杂度太大，会超时

样例：
Sample Input
1 10
10 20
30 40
-1 -1
Sample Output
46
48
52

#include <stdio.h>//调用函数实现递归求范围内数的每一位的和    暗含时间复杂度问题 
long long f(long long a){ 
	if(a==0) return 0;
	else if(a%10) return a%10;//返回个位数 
	else return f(a/10); //返回十位数 
}
long long fact(int n,int m){
	int sum=0,i;
	if(m-n<9) {//范围相差九依次相加 
		for(i=n;i<=m;++i) sum+=f(i);
	}
	while(n%10){//从n到比n大的最小整数个位数的和 
		sum+=f(n);
		n++;
	}
	while(m%10){//从m到比m小的最大整数个位数的和 
		sum+=f(m);
		m--;
	}
	sum+=45*(m-1)/10;//n到m之间整十中个位数的和 
	fact(n/10,m/10);//进行下一位的计算 
	return sum; 
} 
int main () {
	int m,n;
	while(~scanf("%d%d",&n,&m)){
		if(n==-1&&m==-1) break;//退出while 
		printf("%lld",fact(n,m));
	}
	return 0;
}