题解 CF495B 【Modular Equations】

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

#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;
}