Advertisement
NgJaBach

BIGNUM

Jun 20th, 2020 (edited)
290
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.42 KB | None
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. #define fi first
  6. #define se second
  7. #define gcd __gcd
  8. const int N=200050,M=1000000007;
  9. const ll INF=1e18+7;
  10.  
  11. int ton(string s){
  12. int ans=0;
  13. for(int i=0;i<s.size();++i){
  14. ans*=10;
  15. ans+=(s[i]-'0');
  16. }
  17. return ans;
  18. }
  19. string tos(int x){
  20. if (x==0) return "0";
  21. string s="";
  22. while(x){
  23. s+=(char)(x%10+'0');
  24. x/=10;
  25. }
  26. reverse(s.begin(),s.end());
  27. return s;
  28. }
  29. bool cmp(string a,string b){ //a>b
  30. if(a.size()==b.size()) return a>b;
  31. return a.size()>b.size();
  32. }
  33. long long snum(string a){
  34. stringstream ss(a);
  35. long long num;
  36. ss>>num;
  37. return num;
  38. }
  39. string mul(string a,string b){
  40. if(a=="0"||b=="0") return "0";
  41. int n=a.size(),m=b.size(),carry=0;
  42. string ans="";
  43. vector<int>res(n+m,0);
  44. reverse(a.begin(),a.end());
  45. reverse(b.begin(),b.end());
  46. for(int i=0;i<n;++i){
  47. for(int j=0;j<m;++j){
  48. res[i+j]+=(a[i]-'0')*(b[j]-'0')+carry;
  49. carry=res[i+j]/10;
  50. res[i+j]%=10;
  51. }
  52. if(carry>0){
  53. res[i+m]+=carry;
  54. carry=0;
  55. }
  56. }
  57. for(int i=0;i<n+m;++i) ans.pb(char(res[i]+'0'));
  58. reverse(ans.begin(),ans.end());
  59. while(*ans.begin()=='0') ans.erase(ans.begin());
  60. return ans;
  61. }
  62. string sub(string a,string b){
  63. if(a==b) return "0";
  64. bool ok=cmp(a,b);
  65. string ans="";
  66. int digit,carry=0,n,m;
  67. if(ok) swap(a,b);
  68. n=a.size(); m=b.size();
  69. reverse(a.begin(),a.end());
  70. reverse(b.begin(),b.end());
  71. for(int i=m;i<n;++i) b.pb('0');
  72. for(int i=0;i<n;++i){
  73. digit=(a[i]-'0')-(b[i]-'0')-carry;
  74. if(digit<0){
  75. carry=1;
  76. digit=10+digit;
  77. }
  78. else{
  79. carry=0;
  80. }
  81. ans.pb(char(digit+'0'));
  82. }
  83. reverse(ans.begin(),ans.end());
  84. while(*ans.begin()=='0') ans.erase(ans.begin());
  85. if(ok) ans="-"+ans;
  86. return ans;
  87. }
  88. string add(string a,string b){
  89. if(a.size()<b.size()) swap(a,b);
  90. int n=a.size(),m=b.size(),digit,carry=0;
  91. string ans="";
  92. reverse(a.begin(),a.end());
  93. reverse(b.begin(),b.end());
  94. for(int i=m;i<n;++i) b+='0';
  95. for(int i=0;i<n;++i){
  96. digit=(a[i]-'0')+(b[i]-'0')+carry;
  97. carry=digit/10;
  98. digit%=10;
  99. ans.pb(char(digit+'0'));
  100. }
  101. if(carry>0) ans.pb(char(carry+'0'));
  102. reverse(ans.begin(),ans.end());
  103. return ans;
  104. }
  105.  
  106. pair<string,ll> div_small(string a,ll b){ // val and mod
  107. ll num=0;
  108. int n=a.size(),pos;
  109. for(int i=0;i<n;++i){
  110. num=num*10+(a[i]-'0');
  111. if(num>=b){
  112. pos=i+1;
  113. break;
  114. }
  115. }
  116. if(num<b) return {"0",num};
  117. string ans="";
  118. ans.pb(char(num/b+'0'));
  119. num%=b;
  120. for(int i=pos;i<n;++i){
  121. num=num*10+(a[i]-'0');
  122. ans.pb(char(num/b+'0'));
  123. num%=b;
  124. }
  125. return {ans,num};
  126. }
  127. pair<string,string> div_big(string a,string b){
  128. string num="";
  129. int n=a.size(),pos;
  130. for(int i=0;i<n;++i){
  131. num.pb(a[i]);
  132. if(!cmp(num,b)){
  133. pos=i+1;
  134. break;
  135. }
  136. }
  137. if(cmp(num,b)) return {"0",num};
  138. string ans="",tmp;
  139. for(int i=100;i>0;--i){
  140. tmp=mul(to_string(i),b);
  141. if(!cmp(num,tmp)){
  142. ans+=to_string(i);
  143. num=sub(num,tmp);
  144. if(num=="0") num.clear();
  145. break;
  146. }
  147. }
  148. for(int i=pos;i<n;++i){
  149. num.pb(a[i]);
  150. if(cmp(num,b)){
  151. ans.pb('0');
  152. continue;
  153. }
  154. for(int j=100;j>0;--j){
  155. tmp=mul(to_string(j),b);
  156. if(!cmp(num,tmp)){
  157. ans+=to_string(j);
  158. num=sub(num,tmp);
  159. if(num=="0") num.clear();
  160. break;
  161. }
  162. }
  163. }
  164. return {ans,num};
  165. }
  166. ll mod(string a,ll b){
  167. ll num=0,n=a.size();
  168. for(int i=0;i<n;++i){
  169. num=(num*10+(a[i]-'0'))%b;
  170. }
  171. return num;
  172. }
  173. ll large_gcd(string a,ll b){
  174. return gcd(mod(a,b),b);
  175. }
  176. int main(){
  177. ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL);
  178. string a,b;
  179. int k;
  180. fflush(stdin); cin>>a;
  181. fflush(stdin); cin>>b;
  182. cout<<cmp(a,b);
  183. return 0;
  184. }
  185. /*
  186. ==================================+
  187. INPUT: |
  188. ------------------------------ |
  189.  
  190. ------------------------------ |
  191. ==================================+
  192. OUTPUT: |
  193. ------------------------------ |
  194.  
  195. ------------------------------ |
  196. ==================================+
  197. */
Advertisement
RAW Paste Data Copied
Advertisement