题目链接:https://www.acwing.com/problem/content/202/
求解同时满足gcd(a0,x)=a1 和 lcm(b0,x)=b1的x的个数
解法是处理出b1所有的约数,逐一检查是否满足上述两个方程,由于采用试除法时间复杂度到了O(n*sqrt(b1)),大约是1e8,无法再给定的时间内通过所有的样例,所以考虑预处理出质因数之后再对b1进行分解质因数,在[1,sqrt(b1)]之间最多只有sqrt(b1)/logsqrt(b1)个质数,所以时间复杂度大约是O(n*sqrt(b1)/logb1),大约是1e7左右,然后使用dfs得出所有的约数,在2e9范围内拥有约数最多的数拥有的约数大约就是1600个,所以dfs的分支是不多的,时间复杂度忽略。然后就是检验过程了,一个数N大约有logN个约数,检验中用到了两次gcd函数,这个函数的时间复杂度有证明是O(logn)的,所以总的时间复杂度就是O(n*sqrt(b1)/logb1+log^2 n)。可以在指定的时间内求解这个问题。
代码:
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std ; #define maxn 45000 typedef long long ll; pair<int,int> factor[50]; vector<int> prime; bool v[maxn+10]; int cntf; int divider[maxn],cntd; int gcd(int a,int b){ return b?gcd(b,a%b):a; } void get_primes(int n){ memset(v,0,sizeof(v)); for(int i=2;i<=n;i++){ if(!v[i])prime.push_back(i); for(int j=i;j<=n/i;j++){ v[j*i]=1; } } } void dfs(int now,int p){//枚举b1所有的约数,总共会产生之多1600个分支 if(now > cntf){ divider[cntd++]=p; return ; } for(int i=0;i<=factor[now].second;i++){ dfs(now+1,p); p*=factor[now].first; } } const int M=50; int main(){ get_primes(maxn);//预处理出根号b1范围内的质数 int a0,b0,a1,b1; int n; cin>>n; while(n--){ scanf("%d%d%d%d",&a0,&a1,&b0,&b1); cntf=0; cntd=0; int b=b1; for(int i=0;prime[i]*prime[i]<=b;i++){ int p=prime[i]; if(b%p==0){ ++cntf; factor[cntf].first=p; int cnt=0; while(b%p==0)cnt++,b/=p; factor[cntf].second=cnt; } } if(b>1)factor[++cntf]=make_pair(b,1);//最多只有一个大于等于根号b的质数 dfs(1,1); int res=0; for(int i=0;i<cntd;i++){ int x=divider[i]; if(gcd(x,a0)==a1 && 1ll*x*b0/gcd(x,b0)==b1){ res++; } } printf("%d ",res); } return 0; }