#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int LL; typedef pair P; typedef pair LP; const int INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i ostream& operator<<(ostream& os,const vector& v1){ int n=v1.size(); for(int i=0;i ostream& operator<<(ostream& os,const pair& p){ os< istream& operator>>(istream& is,vector& v1){ int n=v1.size(); for(int i=0;i>v1[i]; return is; } template istream& operator>>(istream& is,pair& p){ is>>p.first>>p.second; return is; } namespace sol{ vector calc(LL x,LL a){ vector vs; LL i,j; for(i=2;i<1e6 && x>1;i++){ for(j=0;x%i==0;j++)x/=i; if(j)vs.push_back({i,j}); } if(x>1)vs.push_back({x,1}); for(auto& node:vs){ node.second*=a; } sort(vs.begin(),vs.end()); return vs; } void solve(){ int n,m; int i,j,k; LL a,b,c; LL x,y; cin>>x>>a>>y>>b; vector v1=calc(x,a),v2=calc(y,b); n=v2.size(),m=v1.size(); x=-1; for(i=0,j=0;i