LIS & LDS

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int LIS(vector<int> A)
{
    //Longest Increasing Sequence (Not monotically!)
    int size=A.size();
    vector<int> tail(size,0);
    int len,i;
    tail[0] = A[0];
    len = 1;
    for(i=1;i<size;i++)
    {
        if(A[i]<tail[0])
            tail[0] = A[i];     // new smallest value
           
        else if( A[i] >= tail[len-1] )
            tail[len++] = A[i]; // A[i] wants to extend largest subsequence
           
        else
        {
            tail[upper_bound(tail.begin(),tail.begin()+len,A[i])-tail.begin()] = A[i];
        }
           
    }
    return len;
}

int LDS(vector<int> a)
{
    // Longest Decreasing Subsequence (Not Monotically!!)
    int size=a.size(),max=a[0],i;
    for(i=1;i<size;i++)
        if(max<a[i])max=a[i];
    max++;
    for(i=0;i<size;i++)
        a[i]=max-a[i];
    return LIS(a);
}
int main()
{
    int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
       vector<int> b(A,A+9);
    printf("Length of Lis is %d  AND LDS is %d\n",
            LIS(b),LDS(b));
    return 0;
}

Long Multiply

#define LL long long int
LL multiply(LL a, LL b)
  {
       if(b==0)return 0;
       if(b==1)return a;
       LL c=multiply(a,b/2);
       c=(c+c)%m;
       if(b%2!=0)c=(temp+a)%m;
       return c;   
  }

Snippet

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

#define LL long long int
#define mod 1000000007

int main()
{

}

phi (n)

int phi(int m)
{
    int ans = m;
    for(int i = 0; i < pr.size() && m >= pr[i]*pr[i]; i++)
    {
        if(m % pr[i] == 0)
        {
            ans /= pr[i];
            ans *= (pr[i] - 1);
            while(m % pr[i] == 0) m /= pr[i];
        }
    }
    if(m > 1) ans = (ans/m)*(m - 1);
    return ans;
}

Prime Factorize

This snippet puts all primes uptil s in pr and if you want to know the prime factors , it's in pfactors[i]

#define s 100009

vector<int> pfactor[s + 1];
vector<bool> prime(s + 1, true);
vector<int> pr;

void seive()
{
    prime[0] = prime[1] = false;
    for(int i = 2; i <= s; i++)
    {
        if(prime[i])
        {
            pfactor[i].pb(i);
            pr.pb(i);
            for(int j = 2 * i; j <= s; j += i)
            {
                int jj = j;
                while(jj % i == 0)
                {
                    pfactor[j].pb(i);
                    jj /= i;
                }
                prime[j] = false;
            }
        }
    }
}