zancun
#include<bits/stdc++.h>
#define re register
#define il inline
#define debug printf("Now is %d\n",__LINE__);
using namespace std;
#define maxn 105
#define D double
struct ll{
string u;
string d;
bool z;
}aaa[maxn][maxn];
int n;
ll factsub(ll a,ll b);
bool judge(string str)
{
int ls=str.length();
for(int i=0;i<ls;i++)
{
if(str[i]!='0')
{
return false;
}
}
return true;
}
void printll(ll a,string ed){
if(a.z)cout<<"-";
cout<<a.u<<"/"<<a.d<<ed;
return;
}
int sub1(int *a,int *b,int La,int Lb)
{
if(La<Lb) return -1;
if(La==Lb)
{
for(int i=La-1;i>=0;i--)
if(a[i]>b[i]) break;
else if(a[i]<b[i]) return -1;
}
for(int i=0;i<La;i++)
{
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1;i>=0;i--)
if(a[i]) return i+1;
return 0;
}
string div1(string n1,string n2,int nn)
{
const int L=1e5;
string s,v;
int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);
for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
if(La<Lb || (La==Lb && n1<n2)) {
return n1;
}
int t=La-Lb;
for(int i=La-1;i>=0;i--)
{
if(i>=t) b[i]=b[i-t];
else b[i]=0;
}
Lb=La;
for(int j=0;j<=t;j++)
{
int temp;
while((temp=sub1(a,b+j,La,Lb-j))>=0)
{
La=temp;
r[t-j]++;
}
}
for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;
while(!r[i]) i--;
while(i>=0) s+=r[i--]+'0';
i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v="0";
if(nn==1) return s;
if(nn==2) return v;
return "-1";
}
string Big_Gcd(string str1,string str2)
{
string tmp;
while(!judge(str2))
{
tmp=str1;
str1=str2;
str2=div1(tmp,str2,2);
}
return str1;
}
int compare(string str1,string str2)
{
if(str1.length()>str2.length()) return 1;
else if(str1.length()<str2.length()) return -1;
else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
//add:进来的绝对是正整数，所以d和z不用考虑的，但调用要“.u“，
ll add(ll str1,ll str2)//高精度加法
{
ll str;
int len1=str1.u.length();
int len2=str2.u.length();
//前面补0，弄成长度相同
if(len1<len2)
{
for(int i=1;i<=len2-len1;i++)
str1.u="0"+str1.u;
}
else
{
for(int i=1;i<=len1-len2;i++)
str2.u="0"+str2.u;
}
len1=str1.u.length();
int cf=0;
int temp;
for(int i=len1-1;i>=0;i--)
{
temp=str1.u[i]-'0'+str2.u[i]-'0'+cf;
cf=temp/10;
temp%=10;
str.u=char(temp+'0')+str.u;
}
if(cf!=0) str.u=char(cf+'0')+str.u;
str.d="1";//zhongyao!!!
return str;
}
//高精度减法
//只能是两个正数相减，而且要大减小
//sub:进来的绝对是正整数，所以d和z不用考虑的，但调用要“.u“，但输出考虑负数，无需考虑分数问题。判断一下大小就行
ll sub(ll str1,ll str2)//高精度减法
{
bool ffllaagg;
if((str1.u < str2.u && str1.u.size() == str2.u.size()) || str1.u.size() < str2.u.size())swap(str1,str2),ffllaagg=1;//交换完，记得标记
ll str;
int tmp=str1.u.length()-str2.u.length();
int cf=0;
for(int i=str2.u.length()-1;i>=0;i--)
{
if(str1.u[tmp+i]<str2.u[i]+cf)
{
str.u=char(str1.u[tmp+i]-str2.u[i]-cf+'0'+10)+str.u;
cf=1;
}
else
{
str.u=char(str1.u[tmp+i]-str2.u[i]-cf+'0')+str.u;
cf=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(str1.u[i]-cf>='0')
{
str.u=char(str1.u[i]-cf)+str.u;
cf=0;
}
else
{
str.u=char(str1.u[i]-cf+10)+str.u;
cf=1;
}
}
str.u.erase(0,str.u.find_first_not_of('0'));//去除结果中多余的前导0
if(ffllaagg)str.z=1;
if(str.u==""){
str.u="0";str.z=0;
}
str.d="1";//zhongyao!!!
return str;
}
//高精度乘法
//只能是两个正数相乘
//只有mul的2个参数是string，但4个函数的返回值都是ll
ll mul(string str1,string str2)
{
ll str;
if(str1=="0"||str2=="0"){
str.u="0";str.d="1";
return str;
}
int len1=str1.length();
int len2=str2.length();
ll tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr.u="";
int temp=str2[i]-'0';
int t=0;
int cf=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr.u+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(str1[j]-'0')+cf)%10;
cf=(temp*(str1[j]-'0')+cf)/10;
tempstr.u=char(t+'0')+tempstr.u;
}
if(cf!=0) tempstr.u=char(cf+'0')+tempstr.u;
}
str=add(str,tempstr);
}
str.u.erase(0,str.u.find_first_not_of('0'));
str.d="1";//zhongyao!!!
return str;
}
//高精度除法 == 高精度分数化简
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
//div:进来的绝对是正整数，所以d和z不用考虑的，所以d和z调用没用的，但调用要“.u“，但输出考虑分数，无需考虑负数问题。原来的代码不中用，应使用到gcd，其中的“需要高精度减法和乘法”不能调用下面的factsub和factmul
//最后要化简分数，特判 0/2=0/3=...=0/1 problem && -0 problem a/b=(a/gcd)/(b/gcd)需要：高精度gcd&高精度整除-------------现在只剩这里了，明天（12.11）搞（23:49&00:12寄
//void div(string str1,string str2,string "ient,string &residue)
//高精度整除(保证) 注意biggcd只能是大于0的整数，所以要避免负数调用
ll divZ(ll str1,ll str2)
{
ll str;
if(str1.u=="0")//判断被除数是否为0
{
ll q;
q.u="0";
q.d="1";
q.z=0;
return q;
}
else
{
int len1=str1.u.length();
int len2=str2.u.length();
ll tempstr;
tempstr.u.append(str1.u,0,len2-1);
for(int i=len2-1;i<len1;i++)
{
tempstr.u=tempstr.u+str1.u[i];
tempstr.u.erase(0,tempstr.u.find_first_not_of('0'));
if(tempstr.u.empty())
tempstr.u="0";
for(char ch='9';ch>='0';ch--)//试商
{
ll strt,tmp;
strt.u=strt.u+ch;
tmp=mul(str2.u,strt.u);
//cout<<tmp.u<<endl;
if(compare(tmp.u,tempstr.u)<=0)//试商成功
{
str.u=str.u+ch;
//cout<<str.u<<endl;
tempstr=sub(tempstr,tmp);
//cout<<str.u<<"b"<<endl;
break;
}
}
}
//residue=tempstr;
}
//cout<<str.u<<endl;
str.u.erase(0,str.u.find_first_not_of('0'));
if(str.u.empty()) str.u="0";
str.d="1";//zhongyao!!!因为这里是整除
return str;
}
//高精度除法 == 高精度分数化简
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
//div:进来的绝对是正整数，所以d和z不用考虑的，所以d和z调用没用的，但调用要“.u“，但输出考虑分数，无需考虑负数问题。原来的代码不中用，应使用到gcd，其中的“需要高精度减法和乘法”不能调用下面的factsub和factmul
//最后要化简分数，特判 0/2=0/3=...=0/1 problem && -0 problem a/b=(a/gcd)/(b/gcd)需要：高精度gcd&高精度整除-------------现在只剩这里了，明天（12.11）搞（23:49&00:12寄
//void div(string str1,string str2,string "ient,string &residue)
//分数化简部分 注意biggcd只能是大于0的整数，所以要避免负数调用
ll div(ll str1,ll str2){
if(str1.u=="0"){
ll str;
str.u="0";str.d="1";str.z=0;
return str;
}
ll gcd;
gcd.u=Big_Gcd(str1.u,str2.u);
gcd.d=1;
//cout<<str1.u<<" "<<gcd.u<<endl;
ll uu=divZ(str1,gcd);
ll dd=divZ(str2,gcd);
ll str;
str.u=uu.u;
str.d=dd.u;
return str;
}
//factadd:如果a,b大于0：a/b+c/d=(ad+bc)/bd;化简在div里面完成 a<0:b-a b<0:a-b a,b<0:return -(a+b)--->直接在最后改符号
//factsub：和上面差不多，b情况反过来。满足a-b的，不能直接改符号套进add，要不然add那里有可能又调回来。 记得判断a<b。a/b-c/d=(ad-bc)/bd
//factmul：同样有负数判断，但是变成奇负偶正，不用太麻烦，但是还是很重要的。a/b*c/d=ac/bd
//factdiv：最后化简分数，(a/b)/(c/d)=ad/bc。但是多数情况b和d都是1（小声 化简gcd在上面，记得两个负数相除就要改正数，应该就行了
ll factadd(ll a,ll b){
//cout<<a.z<<"*12345*"<<b.z<<endl;
if(a.z){
if(b.z){
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factadd(aa,bb);
cc.z=1;
return cc;
}else{
return factsub(b,a);
}
}else{
if(b.z){
return factsub(a,b);
}else{
ll ad=mul(a.u,b.d);//+
ll bc=mul(b.u,a.d);//+
ll up=add(ad,bc);//+
//printll(up,"\n");
ll bd=mul(a.d,b.d);//+
//printll(bd,"\n");
ll cc=div(up,bd);//+
return cc;
}
}
}
//factadd:如果a,b大于0：a/b+c/d=(ad+bc)/bd;化简在div里面完成 a<0:b-a b<0:a-b a,b<0:return -(a+b)--->直接在最后改符号
//factsub：和上面差不多，b情况反过来。满足a-b的，不能直接改符号套进add，要不然add那里有可能又调回来。 记得判断a<b。a/b-c/d=(ad-bc)/bd
//factmul：同样有负数判断，但是变成奇负偶正，不用太麻烦，但是还是很重要的。a/b*c/d=ac/bd
//factdiv：最后化简分数，(a/b)/(c/d)=ad/bc。但是多数情况b和d都是1（小声 化简gcd在上面，记得两个负数相除就要改正数，应该就行了
ll factsub(ll a,ll b){
if(a.z){
if(b.z){
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factsub(bb,aa);
return cc;
}else{
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factadd(aa,bb);
cc.z=1;
return cc;
}
}else{
if(b.z){
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factadd(aa,bb);
return cc;
}else{
bool tmp;
ll ad=mul(a.u,b.d);//+
ll bc=mul(b.u,a.d);//+
ll up=sub(ad,bc);//zheli xuyao panduan
if(up.z)tmp=1,up.z=0;
ll bd=mul(a.d,b.d);//+
ll cc=div(up,bd);//+
if(tmp)cc.z=1;
return cc;
}
}
}
//factadd:如果a,b大于0：a/b+c/d=(ad+bc)/bd;化简在div里面完成 a<0:b-a b<0:a-b a,b<0:return -(a+b)--->直接在最后改符号
//factsub：和上面差不多，b情况反过来。满足a-b的，不能直接改符号套进add，要不然add那里有可能又调回来。 记得判断a<b。a/b-c/d=(ad-bc)/bd
//factmul：同样有负数判断，但是变成奇负偶正，不用太麻烦，但是还是很重要的。a/b*c/d=ac/bd
//factdiv：最后化简分数，(a/b)/(c/d)=ad/bc。但是多数情况b和d都是1（小声 化简gcd在上面，记得两个负数相除就要改正数，应该就行了
ll factmul(ll a,ll b){
if((int)(a.z)+(int)(b.z)==1){
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factmul(aa,bb);
cc.z=1;
return cc;
}
return div(mul(a.u,b.u),mul(a.d,b.d));
}
ll factdiv(ll a,ll b){
//cout<<endl<<a.u<<"/"<<b.u<<" "<<((int)(a.z)+(int)(b.z)==1)<<endl;
if((int)(a.z)+(int)(b.z)==1){
ll aa=a,bb=b;
aa.z=bb.z=0;
ll cc=factdiv(aa,bb);
cc.z=1;
return cc;
}
//cout<<a.u<<b.d<<mul(a.u,b.d).u<<endl;
//cout<<a.d<<b.u<<mul(a.d,b.u).u<<endl;
return div(mul(a.u,b.d),mul(a.d,b.u));
}
//------------------------------------------
/*
string poww(string a,int c){//这个有问题
string b;
b=a;
for(int j=0;j<c-1;j++)
{
string daan="";
int jw=0;
for(int i=a.length()-1;i>=0;i--)
{
int ta,tb;
ta=a[i]-48;
tb=b[i]-48;
int td;
td=((ta+tb+jw)%10);
if(td==0)jw++;
if(ta+tb<10)jw=0;
else jw=1;
daan=daan.insert(0,1,(char)td+48);
}
if(jw>0)daan=daan.insert(0,1,jw+48);
a=daan;
b=daan;
}
if(c!=0)return a;
return "1";
}
*/
ll poww(string a,int b){
//a的b次方
ll s;s.u="1";s.d="1";
for(int ii=0;ii<b;ii++){
s=mul(s.u,a);
}return s;
}
int main()
{
ios::sync_with_stdio(0);
/*
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>aaa[i][n+1].u;
if(aaa[i][n+1].u[0]=='-')aaa[i][n+1].z=1,aaa[i][n+1].u=aaa[i][n+1].u.substr(1,aaa[i][n+1].u.length());
aaa[i][n+1].d="1";
aaa[i][n+1].z=0;
}
for(re int i=1;i<=n;++i)
{
for(re int j=1;j<=n;++j)
{//i^(n-j)
stringstream ss;
string strtmp;
ss<<i;
ss>>strtmp;
aaa[i][j]=poww(strtmp,n-j);
// aaa[i][j].d="1";
cout<<i<<" "<<n-j<<" "<<aaa[i][j].u<<endl;
}
}
cout<<"debug1"<<endl;
for(re int i=1;i<=n;++i)//枚举列（项）
{
re int max=i;
cout<<"debug2"<<endl;
for(re int j=i+1;j<=n;++j)//选出该列最大系数
{
if((aaa[max][i].u < aaa[j][i].u && aaa[max][i].u.size() == aaa[j][i].u.size()) || aaa[max][i].u.size() < aaa[j][i].u.size())
//if(fabs(aaa[j][i])>fabs(aaa[max][i]))
//fabs是取浮点数的绝对值的函数
{
max=j;
}
}
cout<<"debug3"<<endl;
for(re int j=1;j<=n+1;++j)//交换
{
swap(aaa[i][j].u,aaa[max][j].u);
}
/*if(!aaa[i][i])//最大值等于0则说明该列都为0，肯定无解
{
puts("No Solution");
return 0;
}*//*
cout<<"debug4"<<endl;
for(re int j=1;j<=n;++j)//每一项都减去一个数（即加减消元）
{
cout<<"debug5"<<endl;
if(j!=i)
{
cout<<"debug666"<<aaa[j][i].u<<" "<<aaa[i][i].u<<endl;
re ll temp=factdiv(aaa[j][i],aaa[i][i]);
for(re int k=i+1;k<=n+1;++k)
{
cout<<"debug999: "<<aaa[j][k].u<<" "<<aaa[j][k].d<<" "<<aaa[i][k].u<<" "<<temp.u<<endl;
aaa[j][k]=factsub(aaa[j][k],factmul(aaa[i][k],temp));
//a[j][k]-=a[j][i]*a[i][k]/a[i][i];
}
}
for(int ii=1;ii<=n;ii++){
for(int jj=1;jj<=n+1;jj++){
cout<<((aaa[ii][jj].z)?("-"):(" "))<<aaa[ii][jj].u<<"/"<<aaa[ii][jj].d<<" ";
}cout<<endl;
}
}
}
//上述操作结束后，矩阵会变成这样
/*
k1*a=e1
k2*b=e2
k3*c=e3
k4*d=e4
*//*
//所以输出的结果要记得除以该项系数，消去常数
ll ans[maxn];
for(re int i=1;i<=n;++i)
{
ans[i]=factdiv(aaa[i][n+1],aaa[i][i]);
}
//print(ans);
for(int i=1;i<=n;i++){
if(ans[i].z&&ans[i].u!="0")cout<<"-";
cout<<ans[i].u<<"/"<<ans[i].d<<" ";
}*/
ll a,b;a.z=b.z=0;
cin>>a.u>>a.d>>b.u>>b.d;
printll(factdiv(a,b),"\n");
return 0;
}
