Theory:
from 0 to 99 there are 2*10^1=20 for each 0 to 9 digits.
from 0 to 999 there are 3*10^2=300 for each 0 to 9 digits.
so the foemulae is for 0 to n number of 9’s n*10^(n-1) for each 0 to 9 digits.
And so, for upto 445 we can find total number of digits by splitting 445=400+40+5
upto 0 to 400 total number of digits=4*(2*10^1)=80 0 to 9 each and and plus there will 100 of 1 upto 3 each.
so total sum of all the digits 0 upto 400 = 80 + 80*2 + 80*3 + 80*4 +…+80*9 + (1*100 + 2*100 + 3*100) + 4(single most significant digit)=4204
same way 0 to 40 total sum = 4 + 4*2 + 4*3 + ….+ 4*9 + (1*10 + 2*10 + 3*10) + 4 = 244
so from 401 upto 440 there will be additional 40 4’s will be added so 244+40*4=244+160=404
and for 0 to 5 total sum = 0 + (1*1 + 2*1 + 3*1 + 4*1)+5 = 15
so from 441 upto 445 there will be additional (5*2)=10 4’s will be added so 15+40=55
so total sum of digits = 4204+404+25 = 4663
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <string.h> #define lld long long using namespace std; lld Digit[10],Digit2[10]; int getLenth(lld a) { if(a<=9) return 0; int l=0; while(a) { a/=10; l++; } l--; //cout<<l<<"\n"; return l; } int calDigit(lld n,lld digit[10]) { int pwr=-1,msd; lld org=n; lld mult=0; if(n==0) { return 0; } if(n<=9) { for(int i=1;i<=n;i++) digit[i]+=1; return 0; } while(n) { if(n<=9) msd=n; n/=10; mult*=10; pwr++; if(pwr==1) mult=1; } //like 0 to 99 2*1o^1 for each 0 to 9 and for upto 445 or 399 is msd*20=80 ,i.e n*10^(n-1),pwr=n and mult=10^(n-1),,msd = for each msd*(10^n) //cout<<(pwr)*mult<<"\n"; //digit[0]+=(mult*msd); for(int i=0;i<10;i++) digit[i]+=(msd*pwr*mult); for(int i=0;i<msd;i++) digit[i]+=(mult*10);//mult=10^(power-1) digit[msd]+=(org+1-(msd*mult*10)); calDigit(org%(mult*10),digit); return 0; } int main() { lld n,m; //calDigit(1234567,Digit); while(cin>>n) { cin>>m; memset(Digit,0,sizeof(Digit)); memset(Digit2,0,sizeof(Digit2)); if(n==0 && m==0) break; if(n) { calDigit(n-1,Digit); } else Digit[0]=0; calDigit(m,Digit2); lld res =0; for(int i=1;i<10;i++) { res+=((Digit2[i]-Digit[i])*i); } cout<<res<<"\n"; } return 0; } |