「Cfz Round 1」Dead Cells

Luogu

IDLGP9577

Time1000ms

Memory512MB

DifficultyP2

洛谷原创O2优化洛谷月赛

有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。 ## Input 一行 $3$ 个正整数，分别表示 $a,b,k$。 ## Output 一行一个整数，表示答案。 [samples] ## Background Cidoai 上完生物课后，突发奇想出了这么一道题。太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。 ## Note #### 【样例解释 #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$。

Samples

Input #1

3 4 6

Output #1

Input #2

4 7 16

Output #2

Input #3

3 2 5

Output #3

Input #4

114 5141 919810

Output #4

62166352

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments