cp_codes

Primary Template

#include <bits/stdc++.h>
using namespace std;


void solve(){
    
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    uint64_t t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

Square Root using binary search (O(log n))


uint64_t square_root(uint64_t n){
    uint64_t ans;
    uint64_t start = 1, end = n, mid = (n+1)/2;
    while (end - start > 1){
        if (mid*mid < n){
            start = mid;
            mid = (end - start)/2 + start;
        } else if(mid*mid > n){
            end = mid;
            mid = (end - start)/2 + start;
        } else {
            break;
        }
    }
    ans = mid;
    return ans;
}

GCD in log time

uint64_t findgcd(uint64_t a, uint64_t b){
    return b? findgcd(b, a%b): a;
}

Has possible overflow errors, use sqrtl instead.

Binary Exponentiation

uint64_t power(uint64_t a, uint64_t b){
    if (b == 0) return 1;
    uint64_t r = power(a, b/2);
    if (b%2 == 1) return a*r*r;
    return r*r;
}

Binary Search in an array

uint64_t n = 6;
uint64_t arr[n] = {1, 2, 3, 4, 5, 6};
uint64_t start = 0, end = n - 1, mid = start + (end - start)/2;
while (end - start >= 0) {
    mid = start + (end - start)/2
    if (arr[mid] == key) {
        cout << mid << '\n';
        break;
    } else if (arr[mid] < key) start = mid + 1;
    else end = mid - 1;
}
if (arr[mid] != key)
cout << "Not present\n";

Finding powers that are constants

#include <bits/stdc++.h>

template<uint64_t base, uint64_t power> struct power_func {
    static constexpr uint64_t val = base*power_func<base, power - 1>::val;
};

template<uint64_t base> struct power_func<base, 0> {
    static constexpr uint64_t val = 1;
};

See Template Metaprogramming

Seive of Eratosthenes

#include <bits/stdc++.h>

bool p[1000001];
int initmy(){
    p[0] = false; p[1] = false;
    for (uint64_t i = 2; i < 1000001 ; i++) p[i] = true;
    for (int64_t i = 2; i  <= 1000001; i++){
        if (p[i] == 1 && p[i]*p[i] <= 1000001){
            for (uint64_t j = i*i; j <= 1000001; j += i){
                p[j] = false;
            }
        }
    }
    return 1;
}

int trash = 1;

Notes