fork download 
  1. // Big Integer Implementation
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define pb                       push_back
  5. #define all(v)                   v.begin(),v.end()
  6. string roundzero(string x){
  7. 	string ans="";
  8. 	int flag=1;
  9. 	if(x[0]-'0'!=0) flag=0;
  10. 	int i;
  11. 	for(i=0;i<x.length()-1 && flag==1;i++){
  12. 		if(x[i]-'0'!=0) flag=0; 
  13. 	}
  14. 	for(int j=i;j<x.length();j++){
  15. 		ans.pb(x[j]);
  16. 	}
  17. 	return ans;
  18. }
  19. int greater1(string x,string y){
  20.    int i=0;
  21.    while(x[i]==y[i] && i<x.size()){
  22.     i++;
  23.    }
  24.    if(i==x.size()) return -1;
  25.    if(x[i]-'0'>y[i]-'0') return 1;
  26.    else return 0;
  27. }
  28. vector<string> equallength(string x,string y){
  29.     //if(x.size()==y.size()) return;
  30.     if(x.size()>y.size()){
  31.         string temp1=x,temp2=y;
  32.         reverse(all(temp1));
  33.         reverse(all(temp2));
  34.         int u=x.size()-y.size();
  35.         while(u--){
  36.             temp2.pb('0');
  37.         }
  38.         reverse(all(temp1));
  39.         reverse(all(temp2));
  40.         x=temp1;
  41.         y=temp2;
  42.     }
  43.     if(y.size()>x.size()){
  44.         string temp1=x,temp2=y;
  45.         reverse(all(temp1));
  46.         reverse(all(temp2));
  47.         int u=y.size()-x.size();
  48.         while(u--){
  49.             temp1.pb('0');
  50.         }
  51.         reverse(all(temp1));
  52.         reverse(all(temp2));
  53.         x=temp1;
  54.         y=temp2;
  55.     }
  56.     vector<string> ans;
  57.     ans.pb(x);
  58.     ans.pb(y);
  59.     return ans;
  60. }
  61.  
  62. string add(string x,string y){
  63.        string ans="";
  64.        vector<string> el=equallength(x,y);
  65.        x=el[0];
  66.        y=el[1];
  67.        int carry=0;
  68.        for(int i=x.size()-1;i>=0;i--){
  69.            //cout<<(((x[i]-'0')+(y[i]-'0')+carry)%10)<<endl;
  70.          int ans1=(((x[i]-'0')+(y[i]-'0')+carry)%10);
  71.          ans.pb((char)(ans1+48));
  72.          carry=(x[i]-'0'+y[i]-'0'+carry)/10;
  73.        }
  74.     if(carry!=0)
  75.     ans.pb((char)(carry+48));
  76.     reverse(all(ans));
  77.     return ans;
  78. }
  79.  
  80. string subtract(string x,string y){
  81.     string ans="";
  82.     vector<string> el=equallength(x,y);
  83.     x=el[0];
  84.     y=el[1];
  85.     //cout<<x<<" "<<y<<endl;
  86.     int flag=greater1(x,y);
  87.     //cout<<flag<<endl;
  88.         if(!flag)
  89.         {
  90.             string temp=x;
  91.             x=y;
  92.             y=temp;
  93.         }
  94.         for(int i=x.size()-1;i>=0;i--){
  95.             if(x[i]-y[i]>=0){
  96.                 ans.pb((char)(48+x[i]-y[i]));
  97.             }
  98.             else{
  99.               int r=i-1;
  100.               while(x[r]=='0') r--;
  101.               x[r]=x[r]-1;
  102.               for(int k=r+1;k<i;k++){
  103.                 x[k]='9';
  104.               }
  105.               int p=10+(x[i]-'0');
  106.               int q=y[i]-'0';
  107.               ans.pb((char)(48+(p-q)));
  108.             }
  109.             //cout<<x<<" "<<y<<" "<<ans<<endl;
  110.         }
  111.     reverse(all(ans));
  112.     return ans;
  113.  
  114. }
  115.  
  116. string multiply(string x,string y){
  117.    string ans="";
  118.    for(int i=y.size()-1;i>=0;i--){
  119.     string temp="";
  120.     int e=y.size()-1-i;;
  121.     while(e--) temp.pb('0');
  122.     int p=y[i]-'0';
  123.     int carry=0;
  124.     //cout<<y[i]<<" ";
  125.     for(int j=x.size()-1;j>=0;j--){
  126.         //cout<<x[i]<<" ";
  127.         int q=x[j]-'0';
  128.         int y=((p*q)+carry)%10;
  129.         carry=((p*q)+carry)/10;
  130.         cout<<carry<<" ";
  131.         temp.pb((char)(y+48));
  132.     }
  133.     if(carry!=0)temp.pb((char)(carry+48));
  134.     reverse(all(temp));
  135.     cout<<temp<<endl;
  136.    // cout<<temp<<endl;
  137.     if(ans==""){
  138.         ans=temp;
  139.     }
  140.     else{
  141.         vector<string> el=equallength(temp,ans);
  142.         temp=el[0],ans=el[1];
  143.         ans=add(temp,ans);
  144.     }
  145.    }
  146.    return ans;
  147. }
  148.  
  149. vector<string> divide(string x,string y){
  150. 	 vector<string> ans;
  151. 	 vector<string> el=equallength(x,y);
  152.      x=el[0];
  153.      y=el[1];
  154. 	 string qui="",rem="";
  155.  
  156. 	 if(greater1(x,y)==0) { 
  157. 	 	    qui.pb('0');
  158. 	 	    for(int i=0;i<x.length();i++){
  159. 	 	    	rem.pb(x[i]);
  160. 	 	    }
  161. 	 }
  162. 	 else{
  163. 	 	long long w=0;
  164. 	 	string divid=x;
  165. 	 	string divis=y;
  166. 	 	while(greater1(divid,divis)){
  167. 	 		divid=subtract(divid,divis);
  168. 	 		w++;
  169. 	 	}
  170. 	 	while(w){
  171. 	 		qui.pb((char)(48+(w%10)));
  172. 	 		w/=10;
  173. 	 	}
  174. 	 	reverse(all(qui));
  175. 	 	for(int i=0;i<divid.length();i++){
  176. 	 		rem.pb(divid[i]);
  177. 	 	}
  178. 	 }
  179. 	 ans.pb(qui);
  180. 	 cout<<roundzero(rem)<<endl;
  181. 	 rem=roundzero(rem);
  182. 	 ans.pb(rem);
  183. 	 return ans;
  184. }
  185. int main(){
  186.     string x,y;
  187.    cin>>x>>y;
  188.    vector<string> ans=divide(x,y);
  189.    cout<<ans[0]<<" "<<ans[1]<<endl;
  190. return 0;
  191. }
  192.  
  193.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
3000
56
stdout 
2
53 2
https://ideone.com/Jrxi4d
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!