{"problem":{"name":"[PFOI Round1] 暴龙的火锅","description":{"content":"定义 $S(x)$ 表示 $x$ 的每一位的数字之和，例如：$S(14)=1+4=5$，$S(114514)=1+1+4+5+1+4=16.$ 另外，定义 $fib(x)$ 代表斐波那契数列的第 $x$ 项，具体地： $$fib(1)=fib(2)=1,\\ fib(x)=fib(x-1)+fib(x-2)\\ (x≥3).$$ 现在给定 $n$，求出下式的值，其中 $\\bmod 9$ 表示对 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8377"},"statements":[{"statement_type":"Markdown","content":"定义 $S(x)$ 表示 $x$ 的每一位的数字之和，例如：$S(14)=1+4=5$，$S(114514)=1+1+4+5+1+4=16.$\n\n另外，定义 $fib(x)$ 代表斐波那契数列的第 $x$ 项，具体地：\n\n$$fib(1)=fib(2)=1,\\ fib(x)=fib(x-1)+fib(x-2)\\ (x≥3).$$\n\n现在给定 $n$，求出下式的值，其中 $\\bmod 9$ 表示对 $9$ 取余数：\n\n$$(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \\bmod 9.$$\n\n## Input\n\n第一行一个整数 $T$。\n\n接下来 $T$ 组问询，每次一个整数 $n$。\n\n## Output\n\n$T$ 行，每行一个整数代表答案。\n\n[samples]\n\n## Background\n\n暴龙爱吃火锅。\n\n## Note\n\n【样例解释】\n\n对于第一组询问，$n=7$，答案为： \n\n$$\n\\begin{aligned}\n& \\ \\ \\ \\ \\ (S(fib(1))+S(fib(2))\\ldots+S(fib(6))+S(fib(7)))\\bmod 9 \\\\\n& =(1+1+2+3+5+8+(1+3))\\bmod 9 \\\\\n& =6.\n\\end{aligned}\n$$\n\n---\n\n【数据范围】\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：}T=1,\\ n\\le 10$；\n- $\\texttt{Subtask 2(30 pts)：}T=10^2,\\ n\\le 10^3$；\n- $\\texttt{Subtask 3(60 pts)：}$无特殊限制。\n\n对于 $100\\%$ 的数据，满足 $1\\le T\\le 10^5,\\ 1\\le n\\le 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8377","tags":["数学","洛谷原创","洛谷月赛"],"sample_group":[["3\n7\n14\n114514","6\n5\n8"]],"created_at":"2026-03-03 11:09:25"}}