// Big Integer Implementation
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
// Excluding leading zeroes
string roundzero(string x){
string ans="";
int flag=1;
if(x[0]-'0'!=0) flag=0;
int i;
for(i=0;i<x.length()-1 && flag==1;i++){
if(x[i]-'0'!=0) flag=0;
}
for(int j=i;j<x.length();j++){
ans.pb(x[j]);
}
return ans;
}
// To find greater of two string
int greater1(string x,string y){
int i=0;
while(x[i]==y[i] && i<x.size()){
i++;
}
if(i==x.size()) return -1;
if(x[i]-'0'>y[i]-'0') return 1;
else return 0;
}
// To make strings of equal length
vector<string> equallength(string x,string y){
//if(x.size()==y.size()) return;
if(x.size()>y.size()){
string temp1=x,temp2=y;
reverse(all(temp1));
reverse(all(temp2));
int u=x.size()-y.size();
while(u--){
temp2.pb('0');
}
reverse(all(temp1));
reverse(all(temp2));
x=temp1;
y=temp2;
}
if(y.size()>x.size()){
string temp1=x,temp2=y;
reverse(all(temp1));
reverse(all(temp2));
int u=y.size()-x.size();
while(u--){
temp1.pb('0');
}
reverse(all(temp1));
reverse(all(temp2));
x=temp1;
y=temp2;
}
vector<string> ans;
ans.pb(x);
ans.pb(y);
return ans;
}
//ADD
string add(string x,string y){
string ans="";
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
int carry=0;
for(int i=x.size()-1;i>=0;i--){
//cout<<(((x[i]-'0')+(y[i]-'0')+carry)%10)<<endl;
int ans1=(((x[i]-'0')+(y[i]-'0')+carry)%10);
ans.pb((char)(ans1+48));
carry=(x[i]-'0'+y[i]-'0'+carry)/10;
}
if(carry!=0)
ans.pb((char)(carry+48));
reverse(all(ans));
return ans;
}
//SUBTRACT
string subtract(string x,string y){
string ans="";
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
//cout<<x<<" "<<y<<endl;
int flag=greater1(x,y);
//cout<<flag<<endl;
if(!flag)
{
string temp=x;
x=y;
y=temp;
}
for(int i=x.size()-1;i>=0;i--){
if(x[i]-y[i]>=0){
ans.pb((char)(48+x[i]-y[i]));
}
else{
int r=i-1;
while(x[r]=='0') r--;
x[r]=x[r]-1;
for(int k=r+1;k<i;k++){
x[k]='9';
}
int p=10+(x[i]-'0');
int q=y[i]-'0';
ans.pb((char)(48+(p-q)));
}
//cout<<x<<" "<<y<<" "<<ans<<endl;
}
reverse(all(ans));
return ans;
}
//MULTIPLY
string multiply(string x,string y){
string ans="";
for(int i=y.size()-1;i>=0;i--){
string temp="";
int e=y.size()-1-i;;
while(e--) temp.pb('0');
int p=y[i]-'0';
int carry=0;
//cout<<y[i]<<" ";
for(int j=x.size()-1;j>=0;j--){
//cout<<x[i]<<" ";
int q=x[j]-'0';
int y=((p*q)+carry)%10;
carry=((p*q)+carry)/10;
cout<<carry<<" ";
temp.pb((char)(y+48));
}
if(carry!=0)temp.pb((char)(carry+48));
reverse(all(temp));
cout<<temp<<endl;
// cout<<temp<<endl;
if(ans==""){
ans=temp;
}
else{
vector<string> el=equallength(temp,ans);
temp=el[0],ans=el[1];
ans=add(temp,ans);
}
}
return ans;
}
//DIVIDE uses repeated subtraction ;;may lead to TLE
vector<string> divide(string x,string y){
vector<string> ans;
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
string qui="",rem="";
if(greater1(x,y)==0) {
qui.pb('0');
for(int i=0;i<x.length();i++){
rem.pb(x[i]);
}
}
else{
long long w=0;
string divid=x;
string divis=y;
while(greater1(divid,divis)){
divid=subtract(divid,divis);
w++;
}
while(w){
qui.pb((char)(48+(w%10)));
w/=10;
}
reverse(all(qui));
for(int i=0;i<divid.length();i++){
rem.pb(divid[i]);
}
}
ans.pb(qui);
cout<<roundzero(rem)<<endl;
rem=roundzero(rem);
ans.pb(rem);
return ans;
}
//Main
int main(){
string x,y;
cin>>x>>y;
vector<string> ans=divide(x,y);
cout<<ans[0]<<" "<<ans[1]<<endl;
return 0;
}
Link To Clipboard
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
// Excluding leading zeroes
string roundzero(string x){
string ans="";
int flag=1;
if(x[0]-'0'!=0) flag=0;
int i;
for(i=0;i<x.length()-1 && flag==1;i++){
if(x[i]-'0'!=0) flag=0;
}
for(int j=i;j<x.length();j++){
ans.pb(x[j]);
}
return ans;
}
// To find greater of two string
int greater1(string x,string y){
int i=0;
while(x[i]==y[i] && i<x.size()){
i++;
}
if(i==x.size()) return -1;
if(x[i]-'0'>y[i]-'0') return 1;
else return 0;
}
// To make strings of equal length
vector<string> equallength(string x,string y){
//if(x.size()==y.size()) return;
if(x.size()>y.size()){
string temp1=x,temp2=y;
reverse(all(temp1));
reverse(all(temp2));
int u=x.size()-y.size();
while(u--){
temp2.pb('0');
}
reverse(all(temp1));
reverse(all(temp2));
x=temp1;
y=temp2;
}
if(y.size()>x.size()){
string temp1=x,temp2=y;
reverse(all(temp1));
reverse(all(temp2));
int u=y.size()-x.size();
while(u--){
temp1.pb('0');
}
reverse(all(temp1));
reverse(all(temp2));
x=temp1;
y=temp2;
}
vector<string> ans;
ans.pb(x);
ans.pb(y);
return ans;
}
//ADD
string add(string x,string y){
string ans="";
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
int carry=0;
for(int i=x.size()-1;i>=0;i--){
//cout<<(((x[i]-'0')+(y[i]-'0')+carry)%10)<<endl;
int ans1=(((x[i]-'0')+(y[i]-'0')+carry)%10);
ans.pb((char)(ans1+48));
carry=(x[i]-'0'+y[i]-'0'+carry)/10;
}
if(carry!=0)
ans.pb((char)(carry+48));
reverse(all(ans));
return ans;
}
//SUBTRACT
string subtract(string x,string y){
string ans="";
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
//cout<<x<<" "<<y<<endl;
int flag=greater1(x,y);
//cout<<flag<<endl;
if(!flag)
{
string temp=x;
x=y;
y=temp;
}
for(int i=x.size()-1;i>=0;i--){
if(x[i]-y[i]>=0){
ans.pb((char)(48+x[i]-y[i]));
}
else{
int r=i-1;
while(x[r]=='0') r--;
x[r]=x[r]-1;
for(int k=r+1;k<i;k++){
x[k]='9';
}
int p=10+(x[i]-'0');
int q=y[i]-'0';
ans.pb((char)(48+(p-q)));
}
//cout<<x<<" "<<y<<" "<<ans<<endl;
}
reverse(all(ans));
return ans;
}
//MULTIPLY
string multiply(string x,string y){
string ans="";
for(int i=y.size()-1;i>=0;i--){
string temp="";
int e=y.size()-1-i;;
while(e--) temp.pb('0');
int p=y[i]-'0';
int carry=0;
//cout<<y[i]<<" ";
for(int j=x.size()-1;j>=0;j--){
//cout<<x[i]<<" ";
int q=x[j]-'0';
int y=((p*q)+carry)%10;
carry=((p*q)+carry)/10;
cout<<carry<<" ";
temp.pb((char)(y+48));
}
if(carry!=0)temp.pb((char)(carry+48));
reverse(all(temp));
cout<<temp<<endl;
// cout<<temp<<endl;
if(ans==""){
ans=temp;
}
else{
vector<string> el=equallength(temp,ans);
temp=el[0],ans=el[1];
ans=add(temp,ans);
}
}
return ans;
}
//DIVIDE uses repeated subtraction ;;may lead to TLE
vector<string> divide(string x,string y){
vector<string> ans;
vector<string> el=equallength(x,y);
x=el[0];
y=el[1];
string qui="",rem="";
if(greater1(x,y)==0) {
qui.pb('0');
for(int i=0;i<x.length();i++){
rem.pb(x[i]);
}
}
else{
long long w=0;
string divid=x;
string divis=y;
while(greater1(divid,divis)){
divid=subtract(divid,divis);
w++;
}
while(w){
qui.pb((char)(48+(w%10)));
w/=10;
}
reverse(all(qui));
for(int i=0;i<divid.length();i++){
rem.pb(divid[i]);
}
}
ans.pb(qui);
cout<<roundzero(rem)<<endl;
rem=roundzero(rem);
ans.pb(rem);
return ans;
}
//Main
int main(){
string x,y;
cin>>x>>y;
vector<string> ans=divide(x,y);
cout<<ans[0]<<" "<<ans[1]<<endl;
return 0;
}
Link To Clipboard
No comments:
Post a Comment