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);
}
//高精度加法
//只能是兩個(gè)正數(shù)相加
//add:進(jìn)來(lái)的絕對(duì)是正整數(shù),所以d和z不用考慮的,但調(diào)用要“.u“,
ll add(ll str1,ll str2)//高精度加法
{
ll str;
int len1=str1.u.length();
int len2=str2.u.length();
//前面補(bǔ)0,弄成長(zhǎng)度相同
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;
}
//高精度減法
//只能是兩個(gè)正數(shù)相減,而且要大減小
//sub:進(jìn)來(lái)的絕對(duì)是正整數(shù),所以d和z不用考慮的,但調(diào)用要“.u“,但輸出考慮負(fù)數(shù),無(wú)需考慮分?jǐn)?shù)問(wèn)題。判斷一下大小就行
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;//交換完,記得標(biāo)記
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'));//去除結(jié)果中多余的前導(dǎo)0
if(ffllaagg)str.z=1;
if(str.u==""){
str.u="0";str.z=0;
}
str.d="1";//zhongyao!!!
return str;
}
//高精度乘法
//只能是兩個(gè)正數(shù)相乘
//只有mul的2個(gè)參數(shù)是string,但4個(gè)函數(shù)的返回值都是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;
}
//高精度除法 == 高精度分?jǐn)?shù)化簡(jiǎn)
//兩個(gè)正數(shù)相除,商為quotient,余數(shù)為residue
//需要高精度減法和乘法
//div:進(jìn)來(lái)的絕對(duì)是正整數(shù),所以d和z不用考慮的,所以d和z調(diào)用沒(méi)用的,但調(diào)用要“.u“,但輸出考慮分?jǐn)?shù),無(wú)需考慮負(fù)數(shù)問(wèn)題。原來(lái)的代碼不中用,應(yīng)使用到gcd,其中的“需要高精度減法和乘法”不能調(diào)用下面的factsub和factmul
//最后要化簡(jiǎn)分?jǐn)?shù),特判 0/2=0/3=...=0/1 problem && -0 problem ? a/b=(a/gcd)/(b/gcd)需要:高精度gcd&高精度整除-------------現(xiàn)在只剩這里了,明天(12.11)搞(23:49&00:12寄
//void div(string str1,string str2,string "ient,string &residue)
//高精度整除(保證) 注意biggcd只能是大于0的整數(shù),所以要避免負(fù)數(shù)調(diào)用
ll divZ(ll str1,ll str2)
{
ll str;
if(str1.u=="0")//判斷被除數(shù)是否為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!!!因?yàn)檫@里是整除
return str;
}
//高精度除法 == 高精度分?jǐn)?shù)化簡(jiǎn)
//兩個(gè)正數(shù)相除,商為quotient,余數(shù)為residue
//需要高精度減法和乘法
//div:進(jìn)來(lái)的絕對(duì)是正整數(shù),所以d和z不用考慮的,所以d和z調(diào)用沒(méi)用的,但調(diào)用要“.u“,但輸出考慮分?jǐn)?shù),無(wú)需考慮負(fù)數(shù)問(wèn)題。原來(lái)的代碼不中用,應(yīng)使用到gcd,其中的“需要高精度減法和乘法”不能調(diào)用下面的factsub和factmul
//最后要化簡(jiǎn)分?jǐn)?shù),特判 0/2=0/3=...=0/1 problem && -0 problem ? a/b=(a/gcd)/(b/gcd)需要:高精度gcd&高精度整除-------------現(xiàn)在只剩這里了,明天(12.11)搞(23:49&00:12寄
//void div(string str1,string str2,string "ient,string &residue)
//分?jǐn)?shù)化簡(jiǎn)部分 注意biggcd只能是大于0的整數(shù),所以要避免負(fù)數(shù)調(diào)用
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;化簡(jiǎn)在div里面完成 ? ? a<0:b-a ? ? b<0:a-b ? ? a,b<0:return -(a+b)--->直接在最后改符號(hào)
//factsub:和上面差不多,b情況反過(guò)來(lái)。滿足a-b的,不能直接改符號(hào)套進(jìn)add,要不然add那里有可能又調(diào)回來(lái)。 記得判斷a<b。a/b-c/d=(ad-bc)/bd
//factmul:同樣有負(fù)數(shù)判斷,但是變成奇負(fù)偶正,不用太麻煩,但是還是很重要的。a/b*c/d=ac/bd
//factdiv:最后化簡(jiǎn)分?jǐn)?shù),(a/b)/(c/d)=ad/bc。但是多數(shù)情況b和d都是1(小聲 ? ? ? ? ? ?化簡(jiǎn)gcd在上面,記得兩個(gè)負(fù)數(shù)相除就要改正數(shù),應(yīng)該就行了
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;化簡(jiǎn)在div里面完成 ? ? a<0:b-a ? ? b<0:a-b ? ? a,b<0:return -(a+b)--->直接在最后改符號(hào)
//factsub:和上面差不多,b情況反過(guò)來(lái)。滿足a-b的,不能直接改符號(hào)套進(jìn)add,要不然add那里有可能又調(diào)回來(lái)。 記得判斷a<b。a/b-c/d=(ad-bc)/bd
//factmul:同樣有負(fù)數(shù)判斷,但是變成奇負(fù)偶正,不用太麻煩,但是還是很重要的。a/b*c/d=ac/bd
//factdiv:最后化簡(jiǎn)分?jǐn)?shù),(a/b)/(c/d)=ad/bc。但是多數(shù)情況b和d都是1(小聲 ? ? ? ? ? ?化簡(jiǎn)gcd在上面,記得兩個(gè)負(fù)數(shù)相除就要改正數(shù),應(yīng)該就行了
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;化簡(jiǎn)在div里面完成 ? ? a<0:b-a ? ? b<0:a-b ? ? a,b<0:return -(a+b)--->直接在最后改符號(hào)
//factsub:和上面差不多,b情況反過(guò)來(lái)。滿足a-b的,不能直接改符號(hào)套進(jìn)add,要不然add那里有可能又調(diào)回來(lái)。 記得判斷a<b。a/b-c/d=(ad-bc)/bd
//factmul:同樣有負(fù)數(shù)判斷,但是變成奇負(fù)偶正,不用太麻煩,但是還是很重要的。a/b*c/d=ac/bd
//factdiv:最后化簡(jiǎn)分?jǐn)?shù),(a/b)/(c/d)=ad/bc。但是多數(shù)情況b和d都是1(小聲 ? ? ? ? ? ?化簡(jiǎn)gcd在上面,記得兩個(gè)負(fù)數(shù)相除就要改正數(shù),應(yīng)該就行了
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){//這個(gè)有問(wèn)題
????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)//枚舉列(項(xiàng))
????{
????????re int max=i;
????????cout<<"debug2"<<endl;
????????for(re int j=i+1;j<=n;++j)//選出該列最大系數(shù)
????????{
????????????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是取浮點(diǎn)數(shù)的絕對(duì)值的函數(shù)
????????????{
????????????????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則說(shuō)明該列都為0,肯定無(wú)解
????????{
????????????puts("No Solution");
????????????return 0;
????????}*//*
????????cout<<"debug4"<<endl;
????????
????????for(re int j=1;j<=n;++j)//每一項(xiàng)都減去一個(gè)數(shù)(即加減消元)
????????{
????????????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;
????????????}
????????}
????}
? ?//上述操作結(jié)束后,矩陣會(huì)變成這樣
? ?/*
? ?k1*a=e1
? ?k2*b=e2
? ?k3*c=e3
? ?k4*d=e4
? ?*//*
? ?//所以輸出的結(jié)果要記得除以該項(xiàng)系數(shù),消去常數(shù)
? ?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;
}