| 题目名称 | 1895. [国家集训队2011]排斥反应 |
|---|---|
| 输入输出 | react.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-12-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：7， 通过率：57.14% | ||||
 514flowey |
100 | 5.117 s | 0.76 MiB | C++ |
 cstdio |
100 | 5.805 s | 0.32 MiB | C++ |
 mikumikumi |
100 | 5.975 s | 0.32 MiB | C++ |
 lichang |
100 | 7.710 s | 0.43 MiB | C++ |
|
cstdio |
95 | 5.787 s | 0.30 MiB | C++ |
|
lichang |
95 | 9.810 s | 0.43 MiB | C++ |
|
cstdio |
0 | 5.903 s | 0.32 MiB | C++ |
| 关于 排斥反应 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
太神了Orzzzzzzzzzzzzzzzzzzzzz
大致思路：p*q矩阵中选若干个数使得不相邻（矩阵是循环的），为什么呢？p,q互质，因此每个数可以用p,q的线性组合唯一表示 | ||||
【问题描述】
在一个圆上均匀分布p*q个点{A1，A2，A3…Ap*q}，Ai与Aj的距离为min{abs(i-j)，p*q-abs(i-j)}，在上面选任意个点(可以选0个)，如果选择的点中存在两个点距离为p或q，就会发生排斥反应，求不发生排斥反应的方案总数。
【输入格式】
输入的第一行包含两个整数，分别表示p和q。
【输出格式】
输出一个整数，表示方案总数，由于这个题答案可能很大，只要输出答案mod 19921107。
【样例输入】
1 6
【样例输出】
18
【数据说明】
对于5%的数据，p=1，q<=1e6；
对于15%的数据，p=1，q<=1e9；
对于100%的数据，p<=10，q<=1e9，p和q互质；
对于100%的数据，时间限制为2s。
【试题来源】
2011中国国家集训队命题答辩