题目大意：给你三个数$n,m,s$，满足$n,m,s≤10^{18}$且最大质因数均不大于$10^6$。
问你存在多少个整数$k$，满足$0≤k≤m$，且$(k,0)$，$(0,n)$，$(x,y)$组成的三角形面积为$s$，其中$x,y$均为整数。
同时，问你存在多少个整数$p$，满足$0≤p<n$，且$(0,0)$，$(0,p)$，$(x,y)$组成的三角形面积为$s$，其中$x,y$均为整数。
请输出两个问题的和。
不超过1000组数据。
对于第一个问题，我们列出三角形面积的式子
s=(s黄+s灰+s蓝+s红)-s灰-s红-s蓝
$s=|\frac{1}{2}nk-\frac{1}{2}x(n-y)-xy-\frac{1}{2}y(k-x)|$
经过化简，有$|k(y-n)+nx|=2s$
若方程有整数解，则有$gcd(k,n)|2s$
我们设$N[i]$表示数字$n$中出现了多少个质因数$p[i],K[i],S[i]$同理。
若$N[i]>S[i]$，那么有$K[i]≤S[i]$。
基于这个性质，我们就可以通过容斥原理来求了，详见代码。
考虑第二个问题，第二个问题显然是求$s$的约数个数，随便搜一下就可以了。
时间复杂度：$O(2^{16}+\sigma(10^{18}))$
#include<bits/stdc++.h>
#define MM 1000005
#define NN 80000
#define L long long
using namespace std; L pow_mod(L x,L k){L ans=; for(;k;k>>=,x=x*x) if(k&) ans=ans*x; return ans;} int pri[MM]={},b[MM]={},use=,last[MM]={},id[MM]={};
void init(){
for(int i=;i<MM;i++){
if(!b[i]) pri[++use]=i,last[i]=,id[i]=use;
for(int j=;j<=use&&i*pri[j]<MM;j++){
b[i*pri[j]]=; last[i*pri[j]]=i;
if(i%pri[j]==) break;
}
}
} int M[NN]={},N[NN]={},S[NN]={};
L a[MM]={},m,n,s,ans=,hh=; void rd(L &res,int cnt[]){
res=;
for(int i=;i<;i++){
int x; scanf("%d",&x);
for(res*=x;x>;x=last[x])
cnt[id[x/last[x]]]++;
}
}
void dfs(L x,L id){
if(id==hh)
return void(ans+=(x<=n));
int ID=a[id];
for(int i=;i<=S[ID];i++){
dfs(x,id+);
x=x*pri[ID];
}
}
void solve(){
memset(M,,sizeof(M)); memset(N,,sizeof(N)); memset(S,,sizeof(S)); ans=hh=;
rd(n,N); rd(m,M); rd(s,S);
s<<=; S[]++;
for(int i=;i<NN;i++) if(N[i]>S[i]) a[hh++]=pow(pri[i],S[i]+);
for(int i=;i<(<<hh);i++){
L mul=,zf=;
for(int j=;j<hh;j++)
if(i&(<<j)){
mul=mul*a[j]; zf=-zf;
}
ans=ans+(m/mul)*zf;
}
hh=; for(int i=;i<NN;i++) if(S[i]) a[hh++]=i;
dfs(,);
printf("%lld\n",ans);
} int main(){
init();
int t; cin>>t;
while(t--) solve();
}