時間限制: 3秒
輸入: int, int
輸入兩個整數 p, q 然後計算出 S(p, q) 的值
$$
\begin{align*}
F(n) = \left\{ \begin{array}{cc}
n\%10 ,& \hspace{5mm} if\quad(n\%10)>0 \\
0,& \hspace{5mm} if \quad n=0 \\
F(n/10),& \hspace{5mm} Otherwise \\
\end{array} \right.
\end{align*}
$$
$$
S(p,q) = \sum_{i=p}^{q} F(i)$$
解題思維
最直觀的想法為用迴圈從 F(s) 不斷的累加直到 F(q) ，不過這樣會超過題目要求的時間。
稍微想下後發現，F(n)的值都介於 0~9 之間
因此可以把F(n)的數列看成這樣:
(0、1、2 ... 8、9)、F(10)、(1 、2 ... 8、9)、F(20) ... (1、2 ... F(n))
然後根據函示 F(n) 的定義如果 n 可以被 10 整除，則 F(n) = F(n/10)
再把上面的式子化簡成下面這樣:
(0、1、2 ... 8、9)、F(1)、(1 、2 ... 8、9)、F(2) ... (1、2 ... F(n))
整理後這樣題目就好解多了!
程式碼解說
這題可以分成三個函式
*回傳的值有可能超過 int 能表示的上限因此用 long long int
- f => 計算 F(n) 的值。
- sum => 計算等差級數的總和。
- f_sum => 計算 S(p, q) 的值，也就是算 F(p) 累加到 F(q) 的總和。
// C++
int f(int n);
long long int sum(int from, int to);
long long int f_sum(int p, int q);
先根據定義寫出一個 F(n) 的函式
// C++
int f(int n)
{
if(n%10) return n%10;
else if(!n) return 0;
else return n/10;
}
再來寫一個計算等差級數總和的函式
// C++
long long int sum(int from, int to)
{
int count = to - from + 1;
return (from+to) * count / 2;
}
接下來寫一個函式計算 S(p, q)
先把結尾是 (1~9) 的數字做一個間隔來切割，如下:
0、(1、2 ... 9)、10、(11、12 ... 19)、20、(21、22 ... 29) ...
如果 p 跟 q 在同一個區間的話則直接累加
// C++
if((p/10) == (q/10))
{
ans += sum(f(p), f(q));
}
若 p 、q 在不同區間的話，先把不能湊成一個完整區間的數字累加起來。
ex:
(8、9)、10、(11、12 ... 18 、 19)、20、(21、22、23)
=> 10、(11、12 ... 18 、 19)、20 為一個完整的區間
=> (8、9) 、 (21、22、23) 不是完整的區間
讓 F(p) 一直累加到 9，並更新 p 的位置到還沒運算的地方
// C++
if(p%10)
{
ans += sum(f(p), 9);
p += (10-p%10);
}
作法跟上面類似，從 1 累加到 F(q)，並更新 q 的位置到還沒運算的地方
// C++
if(q%10){
ans += sum(1, f(q));
q -= q%10;
}
在來用 p、q 來計算之間有幾個間隔，在乘上每個間隔中的總和
// C++
ans += ((q/10 - p/10) * sum(1, 9));
最後再加上 10 的倍數序列 的總和就可以得出答案了
*若 n 是10的倍數 根據 F(n) 定義也就等同於 F(n/10)
// C++
ans += f_sum(p/10, q/10);
