题解：CF678C Joty and Chocolate

HuangBarry · 2024-07-08 16:57:26 · 题解

原题 CF678C Joty and Chocolate

思路：

方法：数学思维。
利用 n \div \operatorname{lcm}(a,b)^{[1]} 算出 1 \sim n 中有多少个既是 a 的倍数也是 b 的倍数。
再利用 n \div a 和 n \div b 分别算出 1 \sim n 中有多少个 a 的倍数和 b 的倍数。
然后细分两种可能，一，{p \le q}^{[2]} 时，两种颜色都可以涂的瓷砖选择涂蓝色，二，{p \ge q}^{[2]} 时，两种颜色都可以涂的瓷砖选择涂红色。

• **注意：`lcm` 函数需要 `C++17`。** 代码如下（不需要吸氧）： ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; ll n,a,b,p,q; ll red;//可以涂成红色的个数(1~n中a的倍数的个数) ll blue;//可以涂成蓝色的个数(1~n中b的倍数的个数) ll both;//既可以涂成红色也可以涂成蓝色的个数(1~n中lcm(a,b)的倍数的个数) int main(){ cin>>n>>a>>b>>p>>q; both=n/(lcm(a,b)); if(p<q){//分情况 red=n/a-both; blue=n/b; } else{ red=n/a; blue=n/b-both; } cout<<red*p+blue*q<<endl; return 0; } ``` [AC 记录](https://www.luogu.com.cn/record/164684704)