Cfz Round 1 - Dead Cells: 细胞分裂模拟 - 代码详解

「Cfz Round 1」Dead Cells - 细胞分裂模拟### 题目背景Cidoai 上完生物课后，突发奇想出了这么一道题。太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。### 题目描述有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。### 输入格式一行 $3$ 个正整数，分别表示 $a,b,k$。### 输出格式一行一个整数，表示答案。### 样例 #1#### 样例输入 #13 4 6#### 样例输出 #12### 样例 #2#### 样例输入 #24 7 16#### 样例输出 #24### 样例 #3#### 样例输入 #33 2 5#### 样例输出 #31### 样例 #4#### 样例输入 #4114 5141 919810#### 样例输出 #462166352### 提示#### 【样例解释 #1】第 $1 /sim 6$ 小时的细胞的数量分别为 $1,1,2,1,1,2$。#### 【数据范围】对于所有数据，$1 /le a,b,k /le 10^6$。本题采用捆绑测试。|子任务编号|分值|$k /le$|特殊性质||:---:|:---:|:---:|:---:||$1$|$15$|$10^6$|保证 $a=b$||$2$|$20$|$10^6$|保证 $a/gt b$||$3$|$25$|$20$|无||$4$|$40$|$10^6$|无|#### 【提示】$/dfrac{a}{2} /equiv a /times 499122177 /pmod {998244353}$，即在对 $998244353$ 取模的情况下，您可以用 $a /times 499122177$ 代替 $a /div 2$。### 代码解析cpp#include using namespace std;int main() { int a, b, k; cin >> a >> b >> k; long long ans = 1; // 存储细胞数量 int mod = 998244353; // 模数 for (int i = 0; i < k; i++) { if (i % a == 0 && i % b == 0) { // 如果时间是 a 和 b 的公倍数，细胞数量不变 continue; } else if (i % a == 0) { // 如果时间是 a 的倍数，细胞数量翻倍 ans = ans * 2 % mod; } else if (i % b == 0) { // 如果时间是 b 的倍数，细胞数量减半 ans = ans * 499122177 % mod; // 使用模运算代替除法 } } cout << ans << endl; return 0