hankson

枫林晚 · 2018-05-02 23:19:29 · 个人记录

#include<bits/stdc++.h>
using namespace std;
const int N=90000+10;
const long long M=2e9+1;
int n;
int pri[N];
int a0,a1,b0,b1;
struct node{
    int top,low,val;
    int can;
}t[N];
int b[N][2],c[N][2];
int cnt,tot;
int s1,s2;
bool vis[N];
void su(){
    for(long long i=2;i*i<=M;i++)
    {
        if(!vis[i]) {
            pri[++cnt]=i;
            for(long long k=i+i;k*k<=M;k+=i)
            {
                vis[k]=1;
            }
        }
        //cout<<"tle"<<endl;
    }
}
void gettop(int p,int q)
{
    memset(b,0,sizeof b);
    memset(c,0,sizeof c);
    s1=s2=0;
    b[++s1][0]=1;
    b[s1][1]=1;
    for(int i=1;(i<=cnt)&&p;i++)
    {
        if(p%pri[i]==0)
        {
        b[++s1][0]=pri[i];
        while(p%pri[i]==0) b[s1][1]++,p/=pri[i];}
    }
    if(p&&p!=1) b[++s1][0]=p,b[s1][1]=1;

    c[++s2][0]=c[s2][1]=1;
    for(int i=1;(i<=cnt)&&q;i++)
    {
        if(q%pri[i]==0)
        {
        c[++s2][0]=pri[i];
        while(q%pri[i]==0) c[s2][1]++,q/=pri[i];}
    }
    if(q) c[++s2][0]=q,c[s2][1]=1;

    int now=1;
    for(int i=1;i<=s2;i++)
    {
        if(c[i][0]>b[now][0]) ++now;
        t[++tot].val=c[i][0];
        if(c[i][0]==b[now][0])
        {
            if(c[i][1]==b[now][1])
             t[tot].top=c[i][1];
            else t[tot].top=c[i][1],t[tot].can=1;
        }
        if(c[i][0]<b[now][0])
        {
            t[tot].can=1;
        }
    }
}
void getlow(int p,int q)
{
    memset(b,0,sizeof b);
    memset(c,0,sizeof c);
    s1=s2=0;
    for(int i=1;(i<=cnt)&&p;i++)
    {
        if(p%pri[i]==0)
        {
        b[++s1][0]=pri[i];
        while(p%pri[i]==0) b[s1][1]++,p/=pri[i];}
    }
    if(p) b[++s1][0]=p,b[s1][1]=1;

    for(int i=1;(i<=cnt)&&q;i++)
    {
        if(q%pri[i]==0)
        {
        c[++s2][0]=pri[i];
        while(q%pri[i]==0) c[s2][1]++,q/=pri[i];}
    }
    if(q) c[++s2][0]=q,c[s2][1]=1;

    int now=1;int wei=1;
    for(int i=1;i<=s2;i++)
    {
        if(b[now][0]<c[i][0]) now++;
        while(t[wei].val<c[i][0]) wei++;
        if(t[wei].val!=c[i][0]) continue;

        if(b[now][0]==c[i][0])
        {
            if(b[now][1]==c[i][1])
             t[wei].low=c[i][1];
            else{
                t[wei].can=1;
            }
        }
        else t[wei].can=1;
    }
}
int main()
{
    cin>>n;
    su();
    for(int i=1;i<=n;i++)
    {
        memset(t,0,sizeof (node));
        tot=0;
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        gettop(b0,b1);
        t[tot+1].val=0x3f3f3f3f;

        cout<<tot<<endl;
        for(int i=1;i<=tot;i++)
         cout<<t[i].val<<" "<<t[i].top<<endl;
        getlow(a1,a0);
        int ans=1;
        for(int i=1;i<=tot;i++)
         if(t[i].can) continue;
         else ans=ans*(t[i].top-t[i].low);
        printf("%d\n",ans);
    }
    return 0;
}