# CF1499D The Number of Pairs【数学】【枚举】【筛素数】

## Description

You are given three positive (greater than zero) integers $c$, $d$ and $x$.

You have to find the number of pairs of positive integers $(a,b)$ such that equality $\newcommand{\lcm}{\mathrm{lcm}}c\cdot \lcm(a,b)-d\cdot\gcd(a,b)=x$ holds. Where $\lcm(a,b)$ is the least common multiple of $a$ and $b$ and $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$.

## Input

The first line contains one integer $t (1\le t\le 10^4)$ — the number of test cases.

Each test case consists of one line containing three integer $c$, $d$ and $x$ $(1\le c,d,x\le 10^7)$.

## Output

For each test case, print one integer — the number of pairs $(a,b)$ such that the above equality holds.

## Example

input

4
1 1 3
4 2 6
3 3 7
2 7 25


output

4
3
0
8


## Note

In the first example, the correct pairs are: $(1,4)$, $(4,1)$, $(3,6)$, $(6,3)$.

In the second example, the correct pairs are: $(1,2)$, $(2,1)$, $(3,3)$.

## 题解

\begin{aligned} \lcm(a,b)&=\frac{x+d\gcd(a,b)}{c}\\ k=\frac{\lcm(a,b)}{\gcd(a,b)}&=\frac{x}{c\gcd(a,b)}+\frac dc \end{aligned}

## Code：

#include<unordered_map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
#ifdef wjyyy
#define gc getchar
#else
#endif
char buf[2100000],*p1=buf,*p2=buf;
using namespace std;
ll Abs(ll x)
{
return x>0?x:-x;
}
{
ll x=0,f=1;
char ch=gc();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=gc();
}
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=gc();
}
return x*f;
}
int pri[2000000],cnt=0,p[20000001];
//pri表示质数列 pi表示i的最小质因子
ll num[20000001];
//numi表示i有多少个不同的质因子
bool is[20000001];
//是否是非质数
ll ans=0,c,d,k;
void work(ll i)
{
if((k+d*i)%c)//求出lcm
return;
ll lcm=(k+d*i)/c;
if(lcm%i)
return;
ll t=lcm/i;
ans+=1<<num[t];
}
int main()
{
is[0]=1;
is[1]=1;
for(int i=2;i<=20000000;++i)
{
if(!is[i])//如果是质数
{
pri[++cnt]=i;
num[i]=1;//它的质因子只有一个
p[i]=i;//它的最小质因子是它自己
}
for(int j=1;j<=cnt&&pri[j]*i<=20000000&&pri[j]<=p[i];++j)
{
int q=pri[j]*i;
is[q]=1;
num[q]=num[i]+(i%pri[j]!=0);//判断是否新增质因子
p[q]=pri[j];
}
}
while(T--)
{
ans=0;
for(int i=1;i*i<=k;++i)
if(k%i==0)
{
work(i);
if(i*i!=k)
work(k/i);
}
printf("%lld\n",ans);
}
return 0;
}


Subscribe

/* */