uva 10994

 1 //组合数学
 2 //计算sum{i从右往左数的第一个非0数字，p<=i<=q}。
 3 #include <cstdio>
 4 typedef long long ll;
 5 
 6 ll sum(ll n)
 7 {
 8     ll ans = 0, x;
 9     while(n)
10     {
11         x = n % 10;
12         n /= 10;
13         ans += ((1 + x) * x) / 2 + n * 45;  //当个位在循环的时候,高位的朋友你在干嘛?
14     }
15     return ans;
16 }
17 
18 int main()
19 {
20     ll a, b;
21     while(scanf("%lld%lld", &a, &b), a >= 0)
22     {
23         printf("%lld
", sum(b) - sum(a - 1));
24     }
25     return 0;
26 }

题目大意：给出l和r，求∑(l≤i≤r)F(i), F(i)函数题目中有。

解题思路：由两边向中间缩进，然后l和r之间的数可以按照1~9划分（只会有这几种情况）。

 1 #include <stdio.h>
 2 #define ll long long
 3 ll ans;
 4 
 5 ll f(ll x) {
 6     if (x == 0)    return 0;
 7     else if (x % 10)
 8         return x % 10;
 9     else
10         return  f(x / 10);
11 }
12 
13 void solve(ll l, ll r) {
14     if (r - l < 9) {
15         for (int i = l; i <= r; i++)
16             ans += f(i);
17         return;
18     }
19 
20     while (l % 10) {
21         ans += f(l);
22         l++;
23     }
24 
25     while (r % 10) {
26         ans += f(r);
27         r--;
28     }
29     ans += 45 * (r - l) / 10;
30     solve(l / 10, r / 10);
31 }
32 
33 int main () {
34     ll l, r;
35     while (scanf("%lld%lld", &l, &r), l >= 0 || r >= 0) {
36         ans = 0;
37         solve(l, r);
38         printf("%lld
", ans);
39     }
40     return 0;
41 }

其實只要看題目推敲一下，大概可以知道其實就是各個數字最低階不是0的數字的總和。

可將題目要加的拆成各個位數來做，每一個位數都要考慮%10和/10的情況要加多少，將這些值全部加起來即可得解。

P.S. 雖然p,q可以在32bits整數下存放，但可沒說總和也可以喔！

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int main(){
 6   long long p, q;
 7   long long sum;
 8 
 9   while( scanf( "%lld%lld", &p, &q ) != EOF && !( p < 0 && q < 0 )){
10     sum = 0;
11 
12     while( p || q ){
13       sum += (q%10+p%10)*((q%10)-(p%10)+1)/2;
14       sum += (q/10-p/10)*45;
15 
16       if( p%10 && (p/10 || q/10) ) p += 10;
17       p /= 10;
18       q /= 10;
19     }
20 
21     printf( "%lld
", sum );
22   }
23   return 0;
24 }