HBC21477晨跑,gcd与exgcd御坂美琴题解（一尺之棰，日取其半）

惰性的成熟算法基础篇 2023-11-09 18:02:01 50 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

misaka是呱太爷爷的小粉丝，呱太爷爷有一句话说的好："一尺之棰，日取其半，万世不竭"，misaka现在有 n 个呱太玩偶放在一堆，每一次操作，misaka会选择当前个数 > 1 的一堆呱太玩偶，并将这一堆呱太玩偶分成。两堆，x 是当前这一堆玩偶的个数，现在 misaka 想将玩偶分成 m 堆，其中第 i 堆呱太玩偶的个数是 ai ，你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆，如果可以输出

misaka是呱太爷爷的小粉丝，呱太爷爷有一句话说的好："一尺之棰，日取其半，万世不竭"。 misaka现在有 n 个呱太玩偶放在一堆，每一次操作，misaka会选择当前个数 > 1 的一堆呱太玩偶。并将这一堆呱太玩偶分成 lfloor frac{x}{2} rfloor ⌊ 2 x ⌋和 x -lfloorfrac{x}{2}rfloor x−⌊ 2 x ⌋ 两堆，x 是当前这一堆玩偶的个数。现在 misaka 想将玩偶分成 m 堆，其中第 i 堆呱太玩偶的个数是 ai ，你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆。如果可以输出 text{misaka} misaka ，否则输出 text{ham} ham 。