Spoj, math: CPCRC1C - Sum of Digits
August 14, 2016
spoj
Primary Problem
给两个数字a和b，求从a到b所有数字的每一位的和。比如1到3就是：1+2+3=6, 10到12
就是：1+0 + 1+1 + 1+2=6，范围是10^9
为了表示方便，用[n]表示从1到n的所有数字的每一位的和。要求从a到b，只需要计算[b] - [a]就可以。
[9] = 45;
[19] = [9] + [9] + 10 * 1 = [9] * 2 + 10 * 1
[99] = [9] + ([9] + 10 * 1) + ([9] + 10 * 2) + ... + ([9] + 10 * 9) =
= [9] * 10 + 10 * [9]
[999] = [99] + ([99] + 100 * 1) + ([99] + 100 * 2) + ([99] + 100 * 3) + ... + ([99] + 100 * 9) =
= [99] * 10 + 100 * [9]
就可以找到规律了：(d是9的个数)
[10^d-1] = [10^(d-1)-1] * 10 + 10^(d-1) * [9]
比如对于457这个数字：
[457] = [399] + (457%100 + 1) * 4 + [57]
= [99] * 4 + 100 * [3] + (457%100 + 1) * 4 + [57]
用d表示数字有多少位，msd表示数的最左边的数字的值，p=10^(d-1)，那么对于任意的n：
[n] = [msd*p - 1] + (n%p+1) * msd + [n%p]
= [p-1] * msd + p * [msd-1] + (n%p+1) * msd + [n%p]
这样问题就解决了。复杂度是O(log(N))
/*
* =====================================================================================
*
* Filename: main1.cpp
*
* Description: http://www.spoj.com/problems/CPCRC1C/
*
* Version: 1.0
* Created: 08/14/2016 20:39:52
* Compiler: g++
*
* Author: Sabastian (liuxueyang.github.io), read3valprintloop@gmail.com
*
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1000000007;
int num_len(int n) {return floor(log10(n))+1;}
ll solve(int n) {
if(n<=0)return 0;
int d=num_len(n);
if(d==1)return (1+n)*n/2;
int p=(int)pow(10,d-1),msd=n/p;
return solve(p-1)*msd+solve(msd-1)*p+(n%p+1)*msd+solve(n%p);
}
int main ( void )
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif /* ----- ONLINE_JUDGE ----- */
int a,b;while(cin>>a>>b&&(a!=-1))cout<<solve(b)-solve(a-1)<<endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
Intermediate
Given Integer A and B, (0<=A,B<=10^15), given Integer k (2<=k<=10). Try to get the sum of digits of numbers from A to B under k-base.
/*
* =====================================================================================
*
* Filename: main.cpp
*
* Description: 给定A，B（A、B < 10^15），求[A,B]内的所有数的
* k(2<=k<=10)进制表示下的个数位之和。
*
* Version: 1.0
* Created: 08/15/2016 11:48:47
* Compiler: g++
*
* Author: Sabastian (liuxueyang.github.io), read3valprintloop@gmail.com
*
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1000000007;
ll getSum1(int n,int k){
// n 是自由位的数目，k是进制，求[0,k^n-1]的所有数字的数位之和.
// eg. [0,99] 那么n=2
return (ll)pow(k,n)*n*(k-1)/2;
}
ll getSum2(int prefix,int n,int k){
// 求小区间的数位和，比如[100,199]
// prefix是公共前缀和，n是自由位数目，k是进制，比如[51000,51999]公
// 共前缀就是5+1=6, n=3, k=10
return getSum1(n,k)+prefix*(ll)pow(k,n);
}
ll getSum3(int prefix,ll n,int k){
// 求[0,n]的在k进制下的数位和，n的范围是10^15，prefix是公共前缀
// 和，n是自由位数目，k是进制
ll ans=0;
if(n<k){rep(i,0,n+1)ans+=i+prefix; return ans;}
int freeNum=(ll)log10(n)/(ll)log10(k),
msd=n/(ll)pow(k,freeNum); // msd is Most Significant Digit
rep(i,0,msd)ans+=getSum2(i+prefix,freeNum,k);
return ans+=getSum3(msd+prefix,n%(ll)pow(k,freeNum),k);
}
ll check(ll n,int k){
ll ans=0;for(ll i=1;i<=n;++i){
ll t=i;while(t){ans+=t%k;t/=k;}
}
return ans;
}
int main ( void )
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif /* ----- ONLINE_JUDGE ----- */
ll a,b;while(cin>>a>>b&&a!=-1){
cout<<getSum3(0,b,10)-getSum3(0,a-1,10)<<endl;
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */