2019年CSP-X复赛真题及题解（T2：鼓掌）
题目描述
运动会上，两个班级在为场上的运动员鼓掌加油。其中 A 班的同学每
x
x
x 秒钟鼓掌一次，B 班的同学每
y
y
y 秒钟鼓掌一次，每次鼓掌都持续
1
1
1 秒钟。这样的话，在
n
n
n 秒钟之内，共有多少秒的时间有掌声？
x
=
2
,
y
=
3
,
n
=
10
x=2,y=3,n=10
x=2,y=3,n=10 的情况如下：
| A | A | A | A | A | |||||
| B | B | B |
共 7 秒有掌声。
输入格式
一行，三个正整数
x
,
y
,
n
x,y,n
x,y,n。
输出格式
一行，一个整数，表示有掌声的时间总长度。
输入输出样例 1
输入 1
2 3 10
输出 1
7
说明/提示
对于
50
%
50\\%
50% 的数据：
0
<
x
,
y
≤
25000
,
n
≤
10
6
0<x,y\\leq 25000,n\\leq 10^6
0<x,y≤25000,n≤106；
对于
100
%
100\\%
100% 的数据：
0
<
x
,
y
≤
40000
,
n
≤
10
9
0<x,y\\leq 40000,n\\leq 10^9
0<x,y≤40000,n≤109。
思路分析
问题转化 每一秒是否有掌声，取决于该秒数（从第 1 秒到第 (n) 秒）能否被 (x) 或 (y) 整除。
- A 班鼓掌时刻：
x
,
2
x
,
3
x
,
…
x, 2x, 3x, \\dots
x,2x,3x,…（≤
n
\\le n
≤n） - B 班鼓掌时刻：
y
,
2
y
,
3
y
,
…
y, 2y, 3y, \\dots
y,2y,3y,…（≤
n
\\le n
≤n）
所以有掌声的秒数就是集合
{
t
∣
1
≤
t
≤
n
,
(
x
∣
t
)
∨
(
y
∣
t
)
}
\\{ t \\mid 1 \\le t \\le n,\\; (x \\mid t) \\lor (y \\mid t) \\}
{t∣1≤t≤n,(x∣t)∨(y∣t)} 的大小。
容斥原理 直接求并集：
ans
=
⌊
n
x
⌋
+
⌊
n
y
⌋
−
⌊
n
lcm
(
x
,
y
)
⌋
\\text{ans} = \\left\\lfloor \\frac{n}{x} \\right\\rfloor + \\left\\lfloor \\frac{n}{y} \\right\\rfloor – \\left\\lfloor \\frac{n}{\\operatorname{lcm}(x,y)} \\right\\rfloor
ans=⌊xn⌋+⌊yn⌋−⌊lcm(x,y)n⌋ 其中
lcm
(
x
,
y
)
=
x
⋅
y
gcd
(
x
,
y
)
\\operatorname{lcm}(x,y) = \\frac{x \\cdot y}{\\gcd(x,y)}
lcm(x,y)=gcd(x,y)x⋅y，表示同时被两者整除的时刻（重复计数）。
复杂度 仅需常数次算术和一次最大公约数计算（欧几里得算法），时间复杂度
O
(
log
min
(
x
,
y
)
)
O(\\log \\min(x,y))
O(logmin(x,y))，空间 O(1)。
代码实现
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}//欧几里得算法
int main(){
int x,y,n;
cin>>x>>y>>n;
int a=n/x;//A班鼓掌次数
int b=n/y;//B班鼓掌次数
int g=gcd(x,y);//最大公约数
int l=x/g*y;//最小公倍数（先除后乘防溢出）
int c=n/l;//同时鼓掌次数
int ans=a+b–c;//容斥结果
cout<<ans;
return 0;
}
功能分析
- 分别计算
⌊
n
/
x
⌋
\\lfloor n/x \\rfloor
⌊n/x⌋、⌊
n
/
y
⌋
\\lfloor n/y \\rfloor
⌊n/y⌋。 - 通过欧几里得算法求
gcd
(
x
,
y
)
\\gcd(x,y)
gcd(x,y)，进而求得lcm
\\operatorname{lcm}
lcm。 - 计算
⌊
n
/
lcm
⌋
\\lfloor n/\\operatorname{lcm} \\rfloor
⌊n/lcm⌋。
更多内容请关注专栏：信奥赛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>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
