bzoj#P2126. 排斥反应

排斥反应

题目描述

在一个圆上均匀分布 p×qp\times q 个点 A1,A2,A3Ap×q{A_1,A_2,A_3\dots A_{p\times q}}AiA_iAjA_j 的距离为 $\min\{\left|(i-j)\right|,p\times q - \left|(i-j)\right|\}$,在上面选任意个点(可以选 00 个),如果选择的点中存在两个点距离为 ppqq,就会发生排斥反应,求不发生排斥反应的方案总数。

输入格式

输入的第一行包含两个整数,分别表示 ppqq

输出格式

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

1 6
18

数据规模与约定

对于 100%100\% 的数据,1p101\le p\le101q1091\le q\le10^9ppqq 互质