企业官网建设流程全解析

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

输入 1

5

输出 1

3

说明/提示

对于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_{k=1}^{i} \text{digit\_sum}(k)∑k=1i​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_{k=1}^{i} k \pmod{3} = \frac{i(i+1)}{2} \pmod{3}∑k=1i​k(mod3)=2i(i+1)​(mod3)。
故第 i 项能被 3 整除当且仅当i ( i + 1 ) 2 ≡ 0 ( m o d 3 ) \frac{i(i+1)}{2} \equiv 0 \pmod{3}2i(i+1)​≡0(mod3)，即i ( i + 1 ) ≡ 0 ( m o d 6 ) i(i+1) \equiv 0 \pmod{6}i(i+1)≡0(mod6)。由于i ( i + 1 ) i(i+1)i(i+1)恒为偶数，故只需i ( i + 1 ) i(i+1)i(i+1)能被 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{n+2}{3}\right\rfloorn−⌊3n+2​⌋。直接计算即可，时间复杂度 O(1)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){longlongn;cin>>n;//读入ncout<<n-(n+2)/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 (n+2)/3 \rfloorn−⌊(n+2)/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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}