{"problem":{"name":"「Cfz Round 1」Dead Cells","description":{"content":"有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。 假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9577"},"statements":[{"statement_type":"Markdown","content":"有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。\n\n假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。\n\n## Input\n\n一行 $3$ 个正整数，分别表示 $a,b,k$。\n\n## Output\n\n一行一个整数，表示答案。\n\n[samples]\n\n## Background\n\nCidoai 上完生物课后，突发奇想出了这么一道题。\n\n太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。\n\n## Note\n\n#### 【样例解释 #1】\n\n第 $1 \\sim 6$ 小时的细胞的数量分别为 $1,1,2,1,1,2$。\n\n#### 【数据范围】\n\n对于所有数据，$1 \\le a,b,k \\le 10^6$。\n\n**本题采用捆绑测试。**\n\n|子任务编号|分值|$k \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|\n|$1$|$15$|$10^6$|保证 $a=b$|\n|$2$|$20$|$10^6$|保证 $a\\gt b$|\n|$3$|$25$|$20$|无|\n|$4$|$40$|$10^6$|无|\n\n#### 【提示】\n\n$\\dfrac{a}{2} \\equiv a \\times 499122177 \\pmod {998244353}$，即在对 $998244353$ 取模的情况下，您可以用 $a \\times 499122177$ 代替 $a \\div 2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9577","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 4 6","2"],["4 7 16","4"],["3 2 5","1"],["114 5141 919810","62166352"]],"created_at":"2026-03-03 11:09:25"}}