hankson
枫林晚
2018-05-02 23:19:29
```cpp
#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;
}
```