洛谷：P1072 Hankson 的趣味题（数学，最大公约数，最小公倍数结合）

题目：

分析：

信息：

1，结果是a1的倍数。

2.倍数不能是:a1/a0分解出来的质因子。

信息：

1，结果是b1的因子。

2，b1/b0一定是结果的因子。

3. b0质数分解也限制了倍数。

我的思路：先求出a1和b1/b0的最小公倍数，这个最小公倍数的倍数就是之后结果。

倍数还应该满足：

1.不能是a1/a0的因数。

2.必须是b0的因数（不准确，先求出a1和b1/b0的最小公倍数，已经用去一部分了）。

有错误：b1/b0的结果是什么？是最终结果必须包含的，但要保证最小公倍数还要继续处理。

放弃了，我的方法需要分解质因子，太复杂了。

题解：

最大公因数：

在此，我就呵呵呵呵。

嗯，其实就是一道简单题。

#include<bits/stdc++.h>
using namespace std;
int m;
int gcd(int a,int b)
{
 return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
 return a/gcd(a,b)*b;
}
int main()
{
 cin>>m;
 for(int i=0;i<m;i++)
 {
  int a0,a1,b0,b1;
  cin>>a0>>a1>>b0>>b1;
  int ans=0; 
  for(int j=1;j<=(int)sqrt(b1);j++)
  {
   if(b1%j!=0) continue;
   if(gcd(a0,j)==a1 && lcm(j,b0)==b1) ans++;
   int j2=b1/(j);
   if(j2==j) continue;
   /*if(b1%(j2)!=0) continue;
   if(j2%a1!=0) continue;*/
   if(gcd(a0,j2)==a1 && lcm(j2,b0)==b1) ans++;
   
  }
  cout<<ans<<endl;
 }
}

之前这样写的，显然不会过的啊：这样就不因该用因子成对出现啊！

总结优化：

因子成对出现，因此可以只找到根号。注意判断因子与对应因子是否相等。

素数筛法。

注意能一起用吗？这个题显然不饿能啊

#include<bits/stdc++.h>
using namespace std;
int m;
int gcd(int a,int b)
{
 return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
 return a/gcd(a,b)*b;
}
int main()
{
 cin>>m;
 for(int i=0;i<m;i++)
 {
  int a0,a1,b0,b1;
  cin>>a0>>a1>>b0>>b1;
  int ans=0; 
  for(int j=1;j*a1<=b1;j++)
  {
   if(b1%(j*a1)!=0) continue;
   if(gcd(a0,(j*a1))==a1 && lcm((j*a1),b0)==b1) ans++;
   int j2=b1/((j*a1));
   //if(j2==(j*a1)) continue;
   /*if(b1%(j2)!=0) continue;
   if(j2%a1!=0) continue;*/
   //if(gcd(a0,j2)==a1 && lcm(j2,b0)==b1) ans++;
  }
  cout<<ans<<endl;
 }
}

这样筛超时了，显然会超时啊，人家对应因子是根号优化的。

另外，发现改为longlong超时，改为int不超时。