Hankson的趣味题

解题记录 数学 算法竞赛进阶指南

题目链接：(AcWing220)Hankson的趣味题

题目大意：

有 $n$ 组数据，每组数据给定 $a_0,a_1,b_0,b_1$，求出满足 $gcd(x,a_0)=a_1, \ lcm(x,b_0)=b_1$ 的 $x$ 数量。

解题思路：

质因数分解。
这道题的关键就在于由 $gcd,\ lcm$ 的性质推导未知数 $x$ 的质因数分解中每个质因子的指数限制。

设 $m_1,m_2,m_3,m_4,m_x$ 分别为 $a_0,a_1,b_0,b_1,x$ 中质因子 $p$ 的次数，可得到以下限制条件。

1. 若 $m_1>m_2$，则 $m_x=m_2$；
2. 若 $m_1=m_2$，则 $m_x\ge m_2$；
3. 若 $m_4>m_3$，则 $m_x=m_4$；
4. 若 $m_4>m_3$，则 $0\le m_x\le m_4$；

上述限制条件可由读者自己根据 $gcd$ 和 $lcm$ 的定义和性质推导或感性理解，本人就不再赘述。其实就是我懒

上述限制分别组合，可得到 4 种情况：

1.$\ m_1>m_2,\ m_4>m_3$
$\ \ \ $若 $m_2=m_4$，则 $m_x=m_2$，否则无解；
2.$\ m_1=m_2,\ m_4>m_3$
$\ \ \ $若 $m_1<m_4$，则 $m_x=m_4$，否则无解；
3.$\ m_1>m_2,\ m_4=m_3$
$\ \ \ $若 $m_2<m_4$，则 $m_x=m_2$，否则无解；
4.$\ m_1=m_2,\ m_4=m_3$
$\ \ \ $若 $m_1<m_4$，则 $m1\le m_x\le m_2$，否则无解；

那我们只需先预处理出一定范围内的质数集合，再对每个质数分别求出 $m_1,m_2,m_3,m_4,m_x$，根据限制条件，把可能的情况相乘就可以得到答案。

代码实现：

PS：这里我没有按上面的方法来求 $m_1,m_2,m_3,m_4,m_x$，导致代码量倍增……，实际上只要在所有质数表里的质数处理完后特判一下（防止 $a_1,b_0$ 本身就是质数）就行了，但是我实在是懒得改了……，贴一个大佬的代码链接吧……Ebola 的博客 题解 P1072 【Hankson 的趣味题】（思路和我的基本一致，可以直接看代码）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define a0 a[0]
#define a1 a[1]
#define b0 a[2]
#define b1 a[3]
#define m1 c[0][now]
#define m2 c[1][now]
#define m3 c[2][now]
#define m4 c[3][now]
using namespace std;
const int N=50000+7;
const int n=50000;
const int test=13;
int T,a[5],c[5][N],res,ans,p[N],cnt,maxn,top,v[N],box[5],nu[5],backup,tag[N],be[N],en[N];
bool flag;
void init(){
    for(int i=2;i<=n;i++){
        if(!v[i]){
            v[i]=i;
            p[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(p[j]>v[i]||i*p[j]>n) break;
            v[i*p[j]]=p[j];
        }
    }
    maxn=p[cnt];
    backup=cnt;
}
void divide(int k){
    int tmp=a[k];
    for(int i=2;i<=sqrt(tmp);i++){
        while(tmp%i==0){
            tmp/=i;
            int t=lower_bound(p+1,p+1+cnt,i)-p;
            top=max(t,top);
            c[k][t]++;
        }
    }
    if(tmp!=1){
        if(tmp<=maxn){
            int t=lower_bound(p+1,p+1+cnt,tmp)-p;
            top=max(t,top);
            c[k][t]++;
        }
        else box[++box[0]]=tmp,nu[box[0]]=k;
    }
}
void extra(){
    for(int i=1;i<=box[0];i++)
        p[++cnt]=box[i];
    sort(p+1,p+1+cnt);
    for(int i=1;i<=box[0];i++){
        int t=lower_bound(p+1,p+1+cnt,box[i])-p;
        top=max(t,top);
        c[nu[i]][t]++;
    }
}
void clear(){
    cnt=backup;
    res=ans=1;
    flag=top=0;
    memset(c,0,sizeof(c));
    memset(box,0,sizeof(box));
    memset(nu,0,sizeof(nu));
}
void run(){
    for(int now=1;now<=top;now++){
        if(m1==m2&&m4==m3){
            if(m1>m4) { flag=1;return; }
            if(m4==0) continue;
            ans*=(m4-m1+1);
        }
        else if(m1>m2&&m4>m3){
            if(m2!=m4) { flag=1;return; }
        }
        else if(m1==m2&&m4>m3){
            if(m4<m1) { flag=1;return; }
        }
        else if(m1>m2&&m4==m3){
            if(m2>m4) { flag=1;return; }
        }
    }
}
void dfs(int now,int res){
    if(now==top+1) { ans++;return; }
    if(tag[now]==4){
        for(int i=be[now];i<=en[now];i++)
            dfs(now+1,res*pow(p[now],i));
    }
    else dfs(now+1,res*pow(p[now],be[now]));
}
int main(){
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    init();
    cin>>T;
    while(T--){
        clear();
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        for(int i=0;i<=3;i++)
            divide(i);
        if(box[0]) extra();
        run();
        if(flag) ans=0;
        printf("%d\n",ans);
    }
}