「Cfz Round 1」Dead Cells

/n

题目背景

/n

Cidoai 上完生物课后，突发奇想出了这么一道题。/n太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。

/n

题目描述

/n

有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。/n假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。

/n

输入格式

/n

一行 $3$ 个正整数，分别表示 $a,b,k$。

/n

输出格式

/n

一行一个整数，表示答案。

/n

样例 #1

/n

样例输入 #1

/n

3 4 6

/n

样例输出 #1

/n

2

/n

样例 #2

/n

样例输入 #2

/n

4 7 16

/n

样例输出 #2

/n

4

/n

样例 #3

/n

样例输入 #3

/n

3 2 5

/n

样例输出 #3

/n

1

/n

样例 #4

/n

样例输入 #4

/n

114 5141 919810

/n

样例输出 #4

/n

62166352

/n

提示

/n

【样例解释 #1】

/n

第 $1 /sim 6$ 小时的细胞的数量分别为 $1,1,2,1,1,2$。

/n

【数据范围】

/n

对于所有数据，$1 /le a,b,k /le 10^6$。

/n

**本题采用捆绑测试。**

/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n/n

子任务编号	分值	$k /le$	特殊性质
$1$	$15$	$10^6$	保证 $a=b$
$2$	$20$	$10^6$	保证 $a/gt b$
$3$	$25$	$20$	无
$4$	$40$	$10^6$	无

/n

【提示】

/n

$/dfrac{a}{2} /equiv a /times 499122177 /pmod {998244353}$，即在对 $998244353$ 取模的情况下，您可以用 $a /times 499122177$ 代替 $a /div 2$。

/n

写出一个正确的C++代码内容：```cpp/n#include /n/nusing namespace std;/n/nconst int MOD = 998244353;/n/nint main() {/n int a, b, k;/n cin >> a >> b >> k;/n/n int ans = 1;/n for (int i = 0; i < k; i++) {/n if ((i % a) == 0) {/n ans = (ans * 2) % MOD;/n } else if ((i % b) == 0) {/n ans = (ans + ans / 2) % MOD;/n }/n }/n/n cout << ans << endl;/n/n return 0;/n}/n```