题解 CF495B 【Modular Equations】
TRZ_2007
2021-01-28 18:36:22
**[题解 CF495B 【Modular Equations】](https://www.luogu.com.cn/problem/CF495B)**
# Solution
分类讨论，对于两个数字的大小关系，很容易分成三类： $a>b,a=n,a<b$。
- 1： $ a > b$ ：
我们考虑题目中给我们的关系式：
$$ a \% x = b$$
转化一下，变成：
$$a = kx + b(k>0)$$
$$kx = a - b$$
所以 $x$ 是 $a - b$ 的因数，我们接下来要求的就是 $a - b$ 的因子个数，时间复杂度 $\mathcal{O(\sqrt{n})}$，思路就是从 1 枚举到 $\sqrt{n}$，看看你枚举的数字能否整除于 $a - b$ ，它和 $n$ 的商能不能整除于 $a - b$ 即可，但是不要忘记 $\sqrt{n}$，这个数字智能做多被记录一次。
**还有一个大前提：x > b!**
- 2： $a = b$：
对于任意一个 $x > a$，题设均成立，所以有无数多个。
- 3： $a < b$：
由于一个数的余数必须小于这个数，所以这种情况不可能。
讨论完了，放代码。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int moder;
int main() {
scanf("%d %d",&n,&m);
if(n < m) printf("0\n");
else if(n == m) {
printf("infinity\n");
} else {
moder = n - m;
for(int i = 1;i * i <= moder;i++) {
// printf("%d\n",i);
if(moder % i == 0) {
ans += (i > m);
if(moder / i > m && moder / i != i) ++ans;
}
}
printf("%d\n",ans);
}
return 0;
}
```