2022年CSP-X复赛真题及题解T1疯狂的数列题目描述在你的帮助下达克终于打开了石门进去后发现里面有个面目狰狞的妖怪。这只妖怪正怒视着轩轩然后一言不发的在地上写了一串数字1 , 12 , 123 , 1234 , 12345 , … , 12345678910 , … , 1234567891011 , … 1,12,123,1234,12345,\dots,12345678910,\dots,1234567891011,\dots1,12,123,1234,12345,…,12345678910,…,1234567891011,…。然后告诉达克“你要是能知道这个数列的前n nn项里有多少项能被3 33整除我就放你过去否则嘿嘿……吃了你”。看来这个妖怪的数学不错。不过数学更是达克的强项很快就算出了答案。你知道怎么算吗?输入格式一个整数n nn。输出格式一个整数表示这个数列的前n nn项里有多少项能被3 33整除。输入输出样例 1输入 15输出 13说明/提示对于30 % 30\%30%的数据满足n ≤ 10 n\leq 10n≤10。对于100 % 100\%100%的数据满足n ≤ 2 31 − 1 n\leq 2^{31}-1n≤231−1。思路分析该数列的第 i 项是将 1 到 i 的所有正整数按顺序拼接而成。一个数能被 3 整除当且仅当其各位数字之和能被 3 整除。拼接后的数字和等于∑ k 1 i digit_sum ( k ) \sum_{k1}^{i} \text{digit\_sum}(k)∑k1i​digit_sum(k)而digit_sum ( k ) ≡ k ( m o d 3 ) \text{digit\_sum}(k) \equiv k \pmod{3}digit_sum(k)≡k(mod3)因此总和模 3 等价于∑ k 1 i k ( m o d 3 ) i ( i 1 ) 2 ( m o d 3 ) \sum_{k1}^{i} k \pmod{3} \frac{i(i1)}{2} \pmod{3}∑k1i​k(mod3)2i(i1)​(mod3)。故第 i 项能被 3 整除当且仅当i ( i 1 ) 2 ≡ 0 ( m o d 3 ) \frac{i(i1)}{2} \equiv 0 \pmod{3}2i(i1)​≡0(mod3)即i ( i 1 ) ≡ 0 ( m o d 6 ) i(i1) \equiv 0 \pmod{6}i(i1)≡0(mod6)。由于i ( i 1 ) i(i1)i(i1)恒为偶数故只需i ( i 1 ) i(i1)i(i1)能被 3 整除即i ≡ 0 i \equiv 0i≡0或i ≡ 2 ( m o d 3 ) i \equiv 2 \pmod{3}i≡2(mod3)。在每连续的三个正整数中恰好有两个满足条件模 3 余 0 或 2一个不满足余 1。因此前 n 项中满足条件的项数为n − ⌊ n 2 3 ⌋ n - \left\lfloor\frac{n2}{3}\right\rfloorn−⌊3n2​⌋。直接计算即可时间复杂度 O(1)。代码实现#includebits/stdc.husingnamespacestd;intmain(){longlongn;cinn;//读入ncoutn-(n2)/3;//输出满足条件的项数return0;}功能分析输入一个整数 n( 1 ≤ n ≤ 2 31 − 1 ) (1 \le n \le 2^{31}-1)(1≤n≤231−1)。处理利用数论规律直接通过公式n − ⌊ ( n 2 ) / 3 ⌋ n - \lfloor (n2)/3 \rfloorn−⌊(n2)/3⌋计算能被3 33整除的项数避免枚举或大数运算。输出符合要求的项数结果在 64 位整数范围内。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}