AtCoder真題及詳細題解 ABC427B： Sum of Digits Sequence
題目描述
對於正整數 
定義一個無限序列
- 對於
，
給定一個正整數 
輸入格式
輸入從標準輸入給出，格式如下：
輸出格式
打印答案。
輸入輸出樣例 1
輸入 1
6輸出 1
23輸入輸出樣例 2
輸入 2
45輸出 2
427説明/提示
樣例解釋 #1
因此，
約束條件
是介於
和
之間的整數，包括
和
。
AC代碼
#include <bits/stdc++.h>
using namespace std;
int n, a[110]; // 定義n和序列a，a[i]存儲序列的第i項
// 計算x的各位數字之和
int f(int x) {
int sum = 0;
while (x) {
sum += x % 10; // 取個位數並累加
x /= 10; // 去掉個位數
}
return sum;
}
int main() {
cin >> n; // 讀入n
a[0] = 1; // 初始化序列的第一項為1
// 計算序列的第1到第n項
for (int i = 1; i <= n; i++) {
a[i] = 0; // 初始化當前項為0
// 累加前i項（索引0到i-1）的各位數字之和
for (int j = 0; j < i; j++) {
a[i] += f(a[j]);
}
}
cout << a[n]; // 輸出序列的第n項
return 0;
}核心邏輯：
- 序列定義：
- A₀ = 1
- 對於i ≥ 1，Aᵢ = f(A₀) + f(A₁) + … + f(Aᵢ₋₁)
- 其中f(x)是x的各位數字之和
- 算法流程：
- 從A₀開始逐個計算序列項
- 對於每個Aᵢ，需要計算前面所有項的各位數字之和
- 使用雙重循環：外層循環遍歷每個位置，內層循環累加前面所有項的f值
時間複雜度：
- 外層循環：O(N)
- 內層循環：O(N)
- 總複雜度：O(N²)，對於N≤100完全可行
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。