题目描述
现在给了a0,a1,b0,b1四个数,问有多少个x满足 gcd(a0,x)=a1,lcm(x,b0)=b1;
样例
输入:
2
41 1 96 288
95 1 37 1776
输出:6 2
算法
由于b1是lcm(x,b0) 那必然x就是b1的约数,所以只要枚举出所有的b1的约束,满足条件的就是x
那如何求b1的约数呢,如果是单纯的暴力那肯定是超时的。
但是我们可以记录所有b1的质因子并且每个质因子的个数,来达到因式分解的目的;
(线性筛的板子写假了 primes写成了bool类型 每个质数都是1抽了一晚的烟都没看出来哪里超时了)
for(int i=1;primes[i]*primes[i]<=h&&i<=cnt;i++)
{
int s=0;
while(h%primes[i]==0) s++,h/=primes[i];
if(s!=0)in[++cntd]={primes[i],s};
}
然后再根据质因子以及每个质因子的个数深搜枚举即可
dfs(1,1);//深搜入口,第1个质因子,当前的值为1
深搜的过程
void dfs(int u,int k){
if(u>cntd) {ans[++cntf]=k;return ;}//如果记录的所有质因子都遍历完那就结束
for(int i=0;i<=in[u].second;i++){
dfs(u+1,k);
k*=in[u].first;//枚举每个因子的数量
}
}
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int cnt=0;
bool st[100010];
int primes[100010];
PII in[100010];
int num[100010];
void init(int k){
for(int i=2;i<=k;i++){
if(!st[i])primes[++cnt]=i;
for(int j=1;i*primes[j]<=k&&j<=cnt;j++){
st[i*primes[j]]=1;
if(i%primes[j]==0) break;
}
}
}
int ans[1000100];
int cntd=0,cntf=0;
void dfs(int u,int k){
if(u>cntd) {ans[++cntf]=k;return ;}
for(int i=0;i<=in[u].second;i++){
dfs(u+1,k);
k*=in[u].first;
}
}
void solve(){
int a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
cntd=0,cntf=0;
int h=b1;
for(int i=1;primes[i]*primes[i]<=b1&&i<=cnt;i++)
{
int s=0;
while(h%primes[i]==0) s++,h/=primes[i];
if(s!=0)in[++cntd]={primes[i],s};
}
if(h>1)in[++cntd]={h,1};
dfs(1,1);
int res=0;
//cout<<cntf<<"+++";
for(int i=1;i<=cntf;i++){
if(__gcd(ans[i],a0)==a1&&(long long)ans[i]*b0/__gcd(ans[i],b0)==b1)
res++;
}
cout<<res<<endl;
}
signed main(){
init(100000);
int _;
cin>>_;
while(_--){
solve();
}
}
所以呢就不快乐。