daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest Apr 16th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Main
  2.  
  3. ```
  4. #include <bits/stdc++.h>
  5. #define MOD 1000000007 
  6. using namespace std;
  7. typedef short i16;
  8. typedef unsigned short u16;
  9. typedef int i32;
  10. typedef unsigned int u32;
  11. typedef long int i64;
  12. typedef unsigned long int u64;
  13. typedef float f32;
  14. typedef double f64;
  15.  
  16. int main(){
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(NULL);
  19.    
  20.     return 0;
  21. }
  22. ```
  23.  
  24. I use Rust data type style because it's more logical and shorter.
  25.  
  26. # Math
  27.  
  28. ## gcd
  29.  
  30. ```
  31. int gcd(int a, int b){
  32.     int temp;
  33.     while (b > 0){
  34.         temp = a%b;
  35.         a = b;
  36.         b = temp;
  37.     }
  38.     return a;
  39. }
  40. ```
  41.  
  42. ## bigint
  43. ```
  44. struct bigint{
  45.     static const int LEN = 60;
  46.     static const int BIGMOD = 10000;
  47.     int s; // sign of big integer
  48.     int vl, v[LEN]; // vl is length of v array
  49.     bigint() : s(1) { vl = 0; } // eg. bigint x;
  50.     bigint(long long a) { // eg. bigint x(a);
  51.     s = 1; vl = 0;
  52.         if (a < 0) {
  53.             s = -1; a = -a;
  54.         }
  55.         while (a) {
  56.             push_back(a % BIGMOD);
  57.             a /= BIGMOD;
  58.         }
  59.     }
  60.     bigint(string str) { // eg. bigint x(str);
  61.     s = 1; vl = 0;
  62.     int stPos = 0, num = 0;
  63.     if (!str.empty() && str[0] == '-') {
  64.         stPos = 1;
  65.         s = -1;
  66.     }
  67.     for (int i=str.length()-1, q=1; i>=stPos; i--) {
  68.         num += (str[i] - '0') * q;
  69.         if ((q *= 10) >= BIGMOD) {
  70.             push_back(num);
  71.             num = 0; q = 1;
  72.         }
  73.     }
  74.     if (num) push_back(num);
  75.     }
  76.     int len() const {
  77.     return vl;
  78.     }
  79.  
  80.     bool empty() const { return len() == 0; }
  81.  
  82.     void push_back(int x) {
  83.     v[vl++] = x;
  84.     }
  85.  
  86.     void pop_back() {
  87.     vl--;
  88.     }
  89.  
  90.     int back() const {
  91.     return v[vl-1];
  92.     }
  93.  
  94.     void n() {
  95.     while (!empty() && !back()) pop_back();
  96.     }
  97.  
  98.     void resize(int nl) {
  99.     vl = nl;
  100.     memset(v,0,sizeof(int)*vl);
  101.     }
  102.     void print() const {
  103.     if (empty()) { putchar('0'); return; }
  104.     if (s == -1) putchar('-');
  105.     printf("%d", back());
  106.     for (int i=len()-2; i>=0; i--) printf("%.4d",v[i]);
  107.     }
  108.  
  109.     friend std::ostream& operator << (std::ostream& out, const bigint &a) {
  110.     if (a.empty()) { out << "0"; return out; }
  111.     if (a.s == -1) out << "-";
  112.     out << a.back();
  113.     for (int i=a.len()-2; i>=0; i--) {
  114.       char str[10];
  115.       snprintf(str, 5, "%.4d", a.v[i]);
  116.       out << str;
  117.     }
  118.     return out;
  119.     }
  120.     int compare(const bigint &b)const {
  121.     if (s != b.s) return s - b.s;
  122.     if (s == -1) return -(-*this).compare(-b);
  123.     if (len() != b.len()) return len()-b.len();//int
  124.     for (int i=len()-1; i>=0; i--)
  125.       if (v[i]!=b.v[i]) return v[i]-b.v[i];
  126.     return 0;
  127.     }
  128.     bool operator < (const bigint &b)const{ return compare(b)<0; }
  129.     bool operator <= (const bigint &b)const{ return compare(b)<=0; }
  130.     bool operator == (const bigint &b)const{ return compare(b)==0; }
  131.     bool operator != (const bigint &b)const{ return compare(b)!=0; }
  132.     bool operator > (const bigint &b)const{ return compare(b)>0; }
  133.     bool operator >= (const bigint &b)const{ return compare(b)>=0; }
  134.     bigint operator - () const {
  135.     bigint r = (*this);
  136.     r.s = -r.s;
  137.     return r;
  138.     }
  139.     bigint operator + (const bigint &b) const {
  140.     if (s == -1) return -(-(*this)+(-b));
  141.     if (b.s == -1) return (*this)-(-b);
  142.     bigint r;
  143.     int nl = max(len(), b.len());
  144.     r.resize(nl + 1);
  145.     for (int i=0; i<nl; i++) {
  146.       if (i < len()) r.v[i] += v[i];
  147.       if (i < b.len()) r.v[i] += b.v[i];
  148.       if(r.v[i] >= BIGMOD) {
  149.         r.v[i+1] += r.v[i] / BIGMOD;
  150.         r.v[i] %= BIGMOD;
  151.       }
  152.     }
  153.     r.n();
  154.     return r;
  155.     }
  156.     bigint operator - (const bigint &b) const {
  157.     if (s == -1) return -(-(*this)-(-b));
  158.     if (b.s == -1) return (*this)+(-b);
  159.     if ((*this) < b) return -(b-(*this));
  160.     bigint r;
  161.     r.resize(len());
  162.     for (int i=0; i<len(); i++) {
  163.       r.v[i] += v[i];
  164.       if (i < b.len()) r.v[i] -= b.v[i];
  165.       if (r.v[i] < 0) {
  166.         r.v[i] += BIGMOD;
  167.         r.v[i+1]--;
  168.       }
  169.     }
  170.     r.n();
  171.     return r;
  172.     }
  173.     bigint operator * (const bigint &b) {
  174.     bigint r;
  175.     r.resize(len() + b.len() + 1);
  176.     r.s = s * b.s;
  177.     for (int i=0; i<len(); i++) {
  178.       for (int j=0; j<b.len(); j++) {
  179.         r.v[i+j] += v[i] * b.v[j];
  180.         if(r.v[i+j] >= BIGMOD) {
  181.           r.v[i+j+1] += r.v[i+j] / BIGMOD;
  182.           r.v[i+j] %= BIGMOD;
  183.         }
  184.       }
  185.     }
  186.     r.n();
  187.     return r;
  188.     }
  189.     bigint operator / (const bigint &b) {
  190.     bigint r;
  191.     r.resize(max(1, len()-b.len()+1));
  192.     int oriS = s;
  193.     bigint b2 = b; // b2 = abs(b)
  194.     s = b2.s = r.s = 1;
  195.     for (int i=r.len()-1; i>=0; i--) {
  196.       int d=0, u=BIGMOD-1;
  197.       while(d<u) {
  198.         int m = (d+u+1)>>1;
  199.         r.v[i] = m;
  200.         if((r*b2) > (*this)) u = m-1;
  201.         else d = m;
  202.       }
  203.       r.v[i] = d;
  204.     }
  205.     s = oriS;
  206.     r.s = s * b.s;
  207.     r.n();
  208.     return r;
  209.     }
  210.     bigint operator % (const bigint &b) {
  211.     return (*this)-(*this)/b*b;
  212.     }
  213. };
  214.  
  215. ```
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top