2020.03.10

Hankson的趣味题 题面

$1<=n<=2000$

$1<=a_0,a_1,b_0,b_1<=10^9×2$


(a,b)=>gcd(a,b),[a,b]=>lcm(a,b)

首先理解题意。给出数据$a,b,c,d$,求满足$(a,x)=b,[c,x]=d$的所有x的个数。

从条件$[c,x]=d$入手,我们可以发现x是d的约数。

于是首先考虑暴力做法,枚举所有x的约数,挨个判断是否满足题目条件,但是不用说,2*1e9的数据铁定T飞。

那么怎么优化呢?

我们可以看到,在我们在求每一组d的所有约数的时候,我们都一定花费了$sqrt(d)$的时间复杂度,而d的范围又比较大,再加上$n$最大可以到2000,所以我们考虑通过其他方式来求得d的所有约数。

于是考虑先对d进行质因式分解,把d拆成$d=p_1^{s_1}×p_2^{s_2}×...×p_n^{s_n}$的形式,其中p为每个质因子,s为每个质因子的次数。这个比较好求,只需要预先把范围以内的质数全部用线性筛过一遍,然后挨个试除,如果有质数p是d的质因子,那就用while循环求出p的次数s即可。

另外,需要注意的是,如果在所有的质因子都已经试除完毕,d的值还大于1,说明他自己也是一个质数(不能通过质数相乘得到),再记录一组{p,s}即{d,1}。注意这里的d是已经被试除过很多次了,所以已经不是输入时候的值了,实现的时候要注意最好先把d存储下来在进行试除,这样不会影响到后面的判断。

接下来我们就可以通过一次暴搜来求得d的所有约数(质因子相乘)并存储下来,作为(a,x)=b,[c,x]=d的x的值的范围,然后枚举判断即可。


#include<bits/stdc++.h>
using namespace std;
int pr[50010],cnt;
bool st[50010];
struct node
{
    int p,s;//质因数和次数
}f[1610];
int fcnt;
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])pr[++cnt]=i;
        for(int j=1;pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/(gcd(a,b))*b;}
int dv[50010],dcnt;
void dfs(int u,int p)//质因子数组下标,x
{
    if(u==fcnt)//搜索结束
    {
        dv[++dcnt]=p;
        return;
    }
    for(int i=0;i<=f[u].s;i++)
    {
        dfs(u+1,p);
        p*=f[u].p;
    }
}
int main()
{
    int n;
    init(50005);
    cin>>n;
    while(n--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        fcnt=0;
        int t=d;
        for(int i=1;pr[i]<=t/pr[i];i++)
        {
            int p=pr[i];
            if(t%p==0)
            {
                int s=0;
                while(t%p==0)
                {
                    t/=p,s++;
                }
                f[fcnt++]={p,s};
            }
            
        }
        if(t>1)f[fcnt++]={t,1};//t本身也是质数
        dcnt=0;
        dfs(0,1);
        int ans=0;
        for(int i=1;i<=dcnt;i++)
        {
            int x=dv[i];
            if(gcd(a,x)==b&&lcm(c,x)==d)ans++;//当前x合法,答案计数加一
        }
        printf("%d\n",ans);
    }
    return 0;
}

最后修改:2020 年 04 月 10 日 05 : 46 PM