当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6427:Problem B. Beads

题目描述
There are m different colors of beads. Define a necklace of length n is a cyclic string that successively connects n beads, taking all rotations and overturnings as equivalent.
For example, [1, 2, 3, 4] is equivalent to [2, 3, 4, 1], [3, 4, 1, 2] and [4, 1, 2, 3] (by ro-tation); and [1, 2, 3, 4] is equivalent to [1, 4, 3, 2], [3, 2, 1, 4], [2, 1, 4, 3] and [4, 3, 2, 1] (by overturning).
Moreover, each time you could transpose the beads of color i to color (i mod m) + 1 for all i at the same time.
After some operations, if a necklace A becomes B, then B is equivalent to A.
Count the number of necklaces modulo 998244353.
输入解释
The first line of the input contains an integer T , denoting the number of test cases.
In each test case, there are two integers n, m in one line, denoting the length of necklaces, and the number of colors.
1 ≤ T ≤ 20, 3 ≤ n ≤ 10^18, 2 ≤ m ≤ 10^18, 998244353 不整除 n, m
输出解释
For each test case, output one line contains a single integer, denoting the number of necklaces modulo 998244353.
输入样例
5
3 2
4 2
8 5
9 5
2333 333
输出样例
2
4
5079
22017
544780894

提示
For n = 3, m = 2:
- [1, 1, 1], [2, 2, 2] are equivalent
- [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2] are equivalent
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6427

最后修改于 2020-10-25T23:31:14+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
8000/4000MS(Java/Others) 524288/524288K(Java/Others)