投資錢景>買台積電就對了5檔高息股比定存強10倍法人:14檔今年本業虧定了24天後重啟院會 兩岸...
2012-03-25 11:47:28 人氣(543) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][Math] 11038 - How Many O's?

0
收藏
0
推薦

Problem E: How many 0's?

A Benedict monk No. 16 writes down the decimal representations of all natural numbers between and including m and n, mn. How many 0's will he write down?

Input consists of a sequence of lines. Each line contains two unsigned 32-bit integers m and n, mn. The last line of input has the value of m negative and this line should not be processed.

For each line of input print one line of output with one integer number giving the number of 0's written down by the monk.

Sample input

10 11
100 200
0 500
1234567890 2345678901
0 4294967295
-1 -1

Output for sample input

1
22
92
987654304
3825876150

做法 by http://www.knightzone.org/wordpress/archives/780
Ex.32053
十位數會出現0的情況=320*10^2
百位數會出現0的情況=(32-1)*10^3+(53+1)

#include <stdio.h>

long long calcZeros(long long n) {
if(n < 0) return 0;
long long sum = 1;
long long n10 = 1, ntail = 0;
while(n) {
if(n%10 != 0) {
sum += n/10*n10;
} else {
sum += (n/10-1)*n10 + (ntail+1);
}
ntail += n%10*n10;
n /= 10, n10 *= 10;
}
return sum;
}
int main() {
long long m, n;
while(scanf("%lld %lld", &m, &n) == 2) {
if(m < 0 && n < 0)
break;
printf("%lld\n", calcZeros(n)-calcZeros(m-1));
}
return 0;
}


11038How Many O's?
台長:Morris
人氣(543) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Math] 11314 - Hardly Hard
此分類上一篇:[UVA][JAVA] 10579 - Fibonacci Numbers

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文