P1072 Hankson的趣味题

趣味题

公式

对于两个正整数 $a$，$b$ 设 $\gcd(a,b)=k$，则存在 $\gcd(\frac{ a }{ k },\frac{ b }{ k })=1$。

$\gcd(\frac{ x }{ a_1 },\frac{ a_0 }{ a_1 })=1$

$\gcd(\frac{ b_1 }{ b_0 },\frac{ b_1 }{ x })=1$

然后通过暴力枚举将因数试出，再带如另一因数，解出答案即可

for(int x=1;x*x<=b1;x++) //暴力枚举 
  if(b1%x==0){
                if(x%a1==0&&gcd(x/a1,p)==1&&gcd(q,b1/x)==1) ans++;//统计 
                int y=b1/x;//找到另一个因子
                if(x==y) continue; //相同跳出 
                if(y%a1==0&&gcd(y/a1,p)==1&&gcd(q,b1/y)==1) ans++;//统计 
            }
        cout<<ans<<endl;//输出 

可以像上面代码一样，对便利范围缩小，进行时间大幅度的优化

这可比全搜一遍快得多

看这两个式子，发现 $x$ 是 $a1$ 的整数倍而且是 $b_1$ 的因子

再看上面两个式子

$\gcd(\frac{ x }{ a_1 },\frac{ a_0 }{ a_1 })=1$

$\gcd(\frac{ b_1 }{ b_0 },\frac{ b_1 }{ x })=1$

发现

$\sqrt b_1$ 枚举 $b_1$ 的因子，也就是 $x$，如果这个数是 $a_1$ 的整数倍并且满足那两个式子，则 ans++

传送门

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
using namespace std;
int gcd(int a,int b){//最大公约数 
  if(b==0){
    return a;
  }
  gcd(b,a%b);
}
int main() {
    int a;
    cin>>a;
    while(a--){//a组数据 
        int a0,a1,b0,b1;
        cin>>a0>>a1>>b0>>b1;//两个式子的数 
        int p=a0/a1,q=b1/b0,ans=0;
        for(int x=1;x*x<=b1;x++) //暴力枚举 
            if(b1%x==0){
                if(x%a1==0&&gcd(x/a1,p)==1&&gcd(q,b1/x)==1) ans++;//统计 
                int y=b1/x;//找到另一个因子
                if(x==y) continue; //相同跳出 
                if(y%a1==0&&gcd(y/a1,p)==1&&gcd(q,b1/y)==1) ans++;//统计 
            }
        cout<<ans<<endl;//输出 
    }
    return 0;
}