#P2126. 排斥反应

    ID: 1149 传统题 2000ms 259MiB 尝试: 357 已通过: 154 难度: 7 上传者: 标签>CF2300提高+/省选-坐标变换独立集状压 DP计数 DP转移矩阵矩阵快速幂

排斥反应

题目描述

在一个圆上均匀分布 p×q 个点 A1​,A2​,A3​…Ap×q​,Ai​ 与 Aj​ 的距离为 min{∣(i−j)∣,p×q−∣(i−j)∣},在上面选任意个点(可以选 0 个),如果选择的点中存在两个点距离为 p 或 q,就会发生排斥反应,求不发生排斥反应的方案总数。

输入格式

输入的第一行包含两个整数,分别表示 p 和 q。

输出格式

输出一个整数,表示方案总数,由于这个题答案可能很大,只要输出答案 mod19921107。

1 6
18

数据规模与约定

对于 100% 的数据,1≤p≤10,1≤q≤109,p 和 q 互质