Hankson的趣味题

HCl_Violet · 2019-11-02 07:31:03 · 题解

传送门：hankson的趣味 （毒瘤） 题

根据以上两个式子，我们可以对a_0,a_1,b_0,b_1进行质因数分解，对每一个p_i分别将其指数记录为num_{a_0},num_{a_1},num_{b_0},num_{b_1};记录x在p_i的指数上能有几种情况；

所以，一个素数表是必不可少的。

然后就是质因数分解啦。

分别记录gcd,lcm公共的种数情况;

接下来分类讨论：

 ①$num_{a_1}=num_{b_1}$ --> 1种

 ②$num_{a_1}>num_{b_1}$ --> 0种

• 如果gcd<lcm,那么此时gcd的情况一定是lcm的子集 --> gcd种

• 如果gcd有无穷种

  ①lcm只有取0这一种 --> 1种

  ②lcm不只取0这一种 --> num_{b_1}-num_{a_1}+1种；

  那么此时应该有6、7两种，即7-6+1；

• 最后，把每一个p_i指数的情况相乘即可

• PS:

  ①如果最后剩余满足b_0=b_1≠1且b_0≠a_0=a_1，否则只有一种（指数取0）,那么剩下的肯定是一个质数，这时p_i指数的取值有2种情况（指数取0或取1）

  ②道理相似,如果最后剩余满足a_0=a_1≠1且a_0≠b_0=b_1,此时应该只有0种情况，否则就有1种情况（指数取0）；

emmm,其实我也不知道对不对。

\mathfrak {Code}:

#include<bits/stdc++.h>
using namespace std;
const int N=50000;
int prime[N],tot;
bool vis[N];

void getprime()
{
    for(int i=2;i<=50000;i++){
        if(!vis[i]){
            prime[++tot]=i;
        }
        for(int j=1;j<=tot&&i*prime[j]<=50000;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}

int work(){
    int ans=1;
    int a,aa,b,bb;
    cin>>a>>aa>>b>>bb;
    if(a<aa||b>bb){
        return 0;
    }
    for(int i=1;i<=tot&&prime[i]<=bb;i++){ 
        int numa=0,numaa=0,numb=0,numbb=0;
        int qcda=1e9,lcmb=1;
        int x=prime[i];
        while(a%x==0){a/=x;numa++;}
        while(aa%x==0){aa/=x;numaa++;}
        while(b%x==0){b/=x;numb++;}
        while(bb%x==0){bb/=x;numbb++;}
        int m;
        if(numa<numaa||numb>numbb){
            return 0;
        }
        if(numa>numaa)qcda=1;
        if(numa==numaa)qcda=1e9;
        if(numb==numbb)lcmb=numbb+1;
        if(numb<numbb)lcmb=1;
        if(numaa>numbb){
            return 0;
        }
        if(lcmb==1&&qcda==1){//都是一种 
            if(numaa==numbb){//如果相同 
                m=1;//就为一种 
            }
            else{//如果不同，0种
                return 0;
            }
        }
        else if(lcmb>qcda){//如果lcm多种，qcd为1种;
        /*因为numbb>=numaa,所以qcd一定是lcm的子集，即m=1*/ 
            m=qcda;
        }
        else if(qcda==1e9&&lcmb>1){//如果qcd为无限种;
        /*例如:qcd中要保证>=6,lcm中要保证<=7,m应该为7-6+1，即2*/ 
            m=numbb-numaa+1;
        }
        else if(lcmb==1&&qcda==1e9){
            m=1;
        }
        ans*=m;
    }
    if(b==bb&&bb!=1&&b!=a&&b!=aa)ans*=2;
    return ans;
}

int main()
{
    getprime();
    int T;
    cin>>T;
    while(T--){
        cout<<work()<<endl;
    }

}