当前位置: 代码迷 >> 综合 >> Codeforces 495B Modular Equations(简单数论)
  详细解决方案

Codeforces 495B Modular Equations(简单数论)

热度:69   发布时间:2024-01-28 04:14:18.0

传送门

题意:求有多少个解(x)。

题解:无法直接枚举。可以看出如果一个x使得等式成立,那么b-a一定是x的倍数,于是枚举一下b-a的因子check一下(是否比b大)即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b;
inline int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*f;
}
int ans;
int main() {a=read(),b=read();if (a<b) puts("0");else if (a==b) puts("infinity");else {int x=a-b;for (int i=1;i*i<=x;++i)if (x%i==0) {int j=x/i;ans+=(i>b);if (j^i) ans+=(j>b);}cout<<ans<<endl;}return 0;
}