题目链接
题意:
给出你 c , d , x c,d,x c,d,x求符合 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的 ( 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 裴蜀定理得到:
x 是 g c d ( l c m ( a , b ) , g c d ( a , b ) ) . x是gcd( lcm(a,b),gcd(a,b) ). x是gcd(lcm(a,b),gcd(a,b)).
而 g c d ( l c m ( a , b ) , g c d ( a , b ) ) 等 于 g c d ( a , b ) . 而gcd( lcm(a,b),gcd(a,b) )等于gcd(a,b). 而gcd(lcm(a,b),gcd(a,b))等于gcd(a,b).
所以说gcd(a,b)是x的因子.所以我们可以枚举x的因子.
lcm=(x+d*gcd)/c
再看lcm/gcd.我们可以知道,是a,b多出来的质因数乘积,所以 质因子只能全部在a或者全部在b,因为我们一定除了gcd(a,b).
那么我们假设lcm/gcd一共n中质因子.那么我们就有2n构造方法.
那么我们就需要筛出2e7内的质因数种数.(利用类似埃式筛)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
#include <set>
#include <map>
#include <queue>
#include <string>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll, ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn = 2e7 + 10;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod = 998244353;
const int MOD = 10007;
int prime[maxn];
ll ans;
#define read read()
void init()
{
for(int i = 2; i < maxn; i++)
{
if(!prime[i])
{
for(int j = i; j < maxn; j += i)
{
prime[j]++;
}
}
}
}
void add(ll gcd,ll x,ll d,ll c)
{
ll lcm=x+d*gcd;
if(lcm%c==0)
{
lcm/=c;
if(lcm%gcd==0)
ans+=1LL<<prime[lcm/gcd];
}
}
void solve()
{
ll d,c,x;
ans=0;
scanf("%lld%lld%lld",&c,&d,&x);
for(int i=1;i<=sqrt(x);i++){
if(x%i==0){
add(i,x,d,c);
if(i*i!=x){
add(x/i,x,d,c);
}
}
}
printf("%lld\n",ans);
}
int main()
{
init();
ll t;
scanf("%lld",&t);
while(t--)
{
solve();
}
return 0;
}