题目链接：点击这里
题目大意：
给定三个正整数
c
,
d
,
x
c,d,x
c,d,x ，求有多少对
a
,
b
a,b
a,b 满足如下式子
c
∗
l
c
m
(
a
,
b
)
−
d
∗
g
c
d
(
a
,
b
)
=
x
c*lcm(a,b)-d*gcd(a,b)=x
c∗lcm(a,b)−d∗gcd(a,b)=x
题目分析：
设
g
c
d
(
a
,
b
)
=
g
gcd(a,b)=g
gcd(a,b)=g ，那么原式等价于
c
∗
a
⋅
b
g
−
d
⋅
g
=
x
c*\frac{a·b}{g}-d·g=x
c∗ga⋅b−d⋅g=x ，化简可得
a
g
⋅
b
g
=
x
g
+
d
c
\frac ag·\frac bg=\frac{\frac xg+d}{c}
ga⋅gb=cgx+d
由于
a
g
,
b
g
\frac ag,\frac bg
ga,gb 是两个互质正整数，所以一定有
g
∣
x
g|x
g∣x ，所以我们就可以枚举
x
x
x 的所有因子
f
a
c
fac
fac，看
f
a
c
+
d
c
\frac {fac+d}{c}
cfac+d 能被拆成多少种两个互质的数的乘积即可。
我们可以想象，若一个数是由
m
m
m 种质因子的幂次乘积构成的，由乘法原理不难发现它可以分成
2
m
2^m
2m 种不同的两个互质的数的乘积
而一个数由多少个质因子可以用埃式筛直接
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O(nloglogn) 预处理得到
总时间复杂度为
O
(
2
e
7
l
o
g
l
o
g
2
e
7
+
t
x
)
O(2e7loglog2e7+t\sqrt x)
O(2e7loglog2e7+tx
)
具体细节见代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
int res = 0,flag = 1;
char ch = getchar();
while(ch<'0' || ch>'9')
{
if(ch == '-') flag = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
{
res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
ch = getchar();
}
return res*flag;
}
const int maxn = 2e7+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
int c,d,x,cnt[maxn];
bool vis[maxn];
void init(int n)
{
for(int i = 2;i <= n;i++)
{
if(!vis[i])
{
cnt[i] = 1;
for(int j = i+i;j <= n;j += i) vis[j] = true,cnt[j]++;
}
}
}
vector<int>fac;
int main()
{
init(maxn-1);
int t = read();
while(t--)
{
int c = read(),d = read(),x = read();
fac.clear();
for(int i = 1;i*i <= x;i++)
{
if(x%i) continue; fac.push_back(i);
if(i*i != x) fac.push_back(x/i);
}
ll ans = 0;
for(auto g:fac)
{
int num = x/g+d;
if(num%c) continue;
ans += 1LL<<cnt[num/c];
}
printf("%lld\n",ans);
}
return 0;
}