http://acm.hdu.edu.cn/showproblem.php?pid=5447
网上好像只找到java的题解，写完就发一下c++代码咯，顺便纪念一下+存个int128板子
做法可以看tjz直播中的pdf：http://www.51nod.com/live/liveDescription.html#!liveId=5
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll MMH
#define ull unsigned long long
using namespace std; inline ull M(ull x,ull MOD){while (x>=MOD)x-=MOD;return x;}
inline ull cheng(ull a,ull b,ull p){
ull mmh=;
while (b){
if (b&) mmh=M(mmh+a,p);
a=M(a+a,p);b>>=;
}
return mmh;
}
char P_C[],O_O[];
char c[]={""};
char ss[][]={"","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""};
inline bool ju(int i){
int cl=strlen(c),sl=strlen(ss[i]);
if (cl<sl) return ;else
if (cl==sl) for (register int j=;j<cl;j++) if (c[j]<ss[i][j]) return ;else if (c[j]>ss[i][j]) break;
for (register int j=;j<cl-sl;j++) c[j]-=;
for (register int j=;j<sl;j++) c[cl-j-]-=ss[i][sl-j-];
for (register int j=;j<cl;j++)
for (register int j=cl-;j;j--)
if (c[j]<) c[j]+=,c[j-]--;
for (i=;c[i]==&&i<cl;i++);
if (i==cl) c[]='',c[]=;else for (register int j=i;j<=cl;j++) c[j-i]=c[j]+;c[cl-i]=;
return ;
}
inline unsigned long long change(){
int cl=strlen(c);
unsigned long long x=;
for (register int i=;i<cl;i++) x*=,x+=c[i]-;
return x;
}
inline void add(int x){
int i;
int cl=strlen(P_C),sl=strlen(ss[x]);
for (i=;i<sl;i++) O_O[i]=ss[x][sl-i-]-;
for (i=;i<cl;i++) O_O[cl-i-]+=P_C[i]-;
if (sl>cl) cl=sl;
for (i=;i<cl;i++)
if (O_O[i]>=) O_O[i+]+=O_O[i]/,O_O[i]%=,cl+=i==(cl-);
for (i=;i<cl;i++) P_C[i]=O_O[cl-i-]+;P_C[cl]=;
}
struct MMH{
unsigned long long a,b;
MMH(ull _a=,ull _b=):a(_a),b(_b){}
void half(){
b>>=;
if (a&) b|=1ull<<;
a>>=;
}
void two(){
a<<=;
if (b&(1ull<<)) a|=;
b<<=;
}
void pr(){
ull A=a,B=b;int s=;
memset(P_C,,sizeof(P_C));
memset(O_O,,sizeof(O_O));
while(B) O_O[s++]=B%+,B/=;P_C[s]=;
for (register int i=;i<s;i++) P_C[i]=O_O[s-i-];
for (register int i=;i<=;i++)
if (A&(1ull<<i)) add(i);
printf("%s ",P_C);
}
};
MMH operator +(const MMH &x,const MMH &y){
MMH z;
z.a=x.a+y.a;z.b=x.b+y.b;if (z.b<x.b||z.b<y.b) z.a++;
return z;
}
MMH operator +(const MMH &x,const int &y){
MMH z=x;
if ((z.b+y)<z.b) z.a++;z.b+=y;
return z;
}
MMH operator -(const MMH &x,const MMH &y){
MMH z;
z.a=x.a-y.a;z.b=x.b-y.b;if (y.b>x.b) z.a--;
return z;
}
MMH operator -(const MMH &x,const int &y){
MMH z=x;
if (z.b<y) z.a--;z.b-=y;
return z;
}
MMH operator *(const MMH &x,const MMH &y){
if (x.a){
MMH z=x,mmh=MMH(,),u=y;
while (u.a|u.b){
if (u.b&) mmh=mmh+z;
z.two();u.half();
}
return mmh;
}
ull s=(1ull<<)-;
ull a=(x.b>>)*(y.b>>),_b1=(x.b&s)*(y.b>>),b=_b1+(x.b>>)*(y.b&s),c=(x.b&s)*(y.b&s),d;
a+=(b<_b1)*1ull<<;
d=c+((b&s)<<);a+=d<c;a+=b>>;
return MMH(a,d);
}
bool operator <(const MMH &x,const MMH &y){return x.a==y.a?x.b<y.b:x.a<y.a;}
bool operator >(const MMH &x,const MMH &y){return x.a==y.a?x.b>y.b:x.a>y.a;}
bool operator !=(const MMH &x,const MMH &y){return x.a!=y.a||x.b!=y.b;}
bool operator ==(const MMH &x,const MMH &y){return x.a==y.a&&x.b==y.b;}
MMH operator %(const MMH &x,const MMH &y){
if (x<y) return x;
MMH z=y,c=x;
while (!(z>c)) z.two();
for(;;){
z.half();
if (!(c<z))c=c-z;
if (z.a==y.a&&z.b==y.b) break;
}
return c;
}
MMH operator /(const MMH &x,const MMH &y){
if (x<y) return MMH{,};
MMH z=y,c=x,a=MMH{,};
while (!(z>x)) z.two();
for(;;){
z.half();a.two();
if (!(c<z))c=c-z,a.b|=;
if (z.a==y.a&&z.b==y.b) break;
}
return a;
}
int operator %(const MMH &x,const int &y){
MMH z=x;
z.a%=y;z.b%=y;
z.a<<=;z.a%=y;
z.a<<=;z.a%=y; z.b+=z.a;if (z.b>=y) z.b-=y;
return z.b;
}
ull sqrt(MMH x){
ull l=,r=1e18,_mid;
MMH mid;
while (l<r){
mid.a=;mid.b=_mid=l+r>>;
mid=mid*mid;
if (x==mid) return _mid;else if (x<mid) r=_mid-;else if (x>mid) l=_mid+;
}
return l;
}
ull sqrt3(MMH x){
ull l=,r=1e12,_mid;
MMH mid=MMH(,);
while (l<r){
mid.a=;mid.b=_mid=l+r>>;
mid=mid*mid*mid;
if (x==mid) return _mid;else if (x<mid) r=_mid-;else if (x>mid) l=_mid+;
}
return l;
}
ull operator %(const MMH &x,const ull &y){
MMH z=x;
z.a%=y;z.b%=y;
for (int i=;i<;i++) z.a<<=,z.a%=y; z.b+=z.a;if (z.b>=y) z.b-=y;
return z.b;
}
inline void read(MMH &n){
scanf("%s",c);
n.a=n.b=;
for (int i=;i>=;i--){
n.a<<=;
if (ju(i)) n.a|=;
}
n.b=change();
}
const int S=;
const ull m_p[]={,,,,,,,,,,,,,,,,,,,};
ll cheng(ll a,ll b,ll p){
ll mmh;mmh=MMH{,};
while (b.a||b.b){
if (b.b&) if (mmh=mmh+a,!(mmh<p)) mmh=mmh-p;
b.half();a=a+a;if (!(a<p)) a=a-p;
}
return mmh;
}
ll mi(ll a,ll b,ll p){
ll mmh;mmh={,};
while (b.a||b.b){
if (b.b&1ull) mmh=cheng(mmh,a,p);
b.half();a=cheng(a,a,p);
}
return mmh;
}
bool prime_judge(ll n){
if(n.b==&&n.a==) return ;
if((n.b<&&n.a==)||!(n.b&)) return ;
for (register int i=;i<S;i++)
if (m_p[i]==n.b&&n.a==) return ;else if (mi(MMH{,(n.a?m_p[i]:m_p[i]%n.b)},n-,n)!=MMH{,}) return ;
return ;
}
ll gcd(ll x,ll y){return (y.a==&&y.b==)?x:gcd(y,x%y);}
ll k1,k2,u;
#define MN 1000001
bool bo[MN];
ull mmh1,mmh2,T,p[MN],num=,A;
inline void work(ll k,ull &mmh,ll u){
if (u.a) return;
ull s=u.b;
if (s<1e8&&k==u*u*u) mmh*=;else
if (k==u*u||(s<=1e8&&k%(s*s)==)) mmh*=;else{
if (k==u) return;
k=k/u;
u=MMH(,sqrt(k));
if (u*u==k) mmh<<=;
}
}
int main(){
register int i,j;
for (i=;i<MN;i++){
if (!bo[i]) p[++num]=i;
for (j=;j<=num&&i*p[j]<MN;j++)
if (bo[i*p[j]]=,i%p[j]==) break;
}
scanf("%d",&T);
while (T--){
read(k1);read(k2);mmh1=mmh2=;
for (i=;i<=num;i++)
if (k1%p[i]==){
A=;k1=k1/MMH{,p[i]};
while (k1%p[i]==) A++,k1=k1/MMH{,p[i]};
mmh1=mmh1*A;
}
for (i=;i<=num;i++)
if (k2%p[i]==){
A=;k2=k2/MMH{,p[i]};
while (k2%p[i]==) A++,k2=k2/MMH{,p[i]};
mmh2=mmh2*A;
} u=gcd(k1,k2);
if (prime_judge(u)) work(k1,mmh1,u),work(k2,mmh2,u);else
if (u!=MMH(,)){
if (A=sqrt(u),u==MMH(,A)*MMH(,A)) mmh1*=(MMH(,A)*u==k1)+,mmh2*=(MMH(,A)*u==k2)+;else
if (A=sqrt3(u),u==MMH(,A)*MMH(,A)*MMH(,A)) mmh1*=,mmh2*=;
}
printf("%llu %llu\n",mmh1,mmh2);
}
}