Program to find last digit of n’th Fibonnaci Number

/*

It takes a while before it is noticeable. In fact, the series is just 60 numbers long and then it repeats the same sequence again and again all the way through the Fibonacci series – for ever. The series of final digits repeats with a cycle length of 60 (Refer this for explanations of this result).
So, instead of calculating the Fibonacci number again and again, pre-compute the units digit of first 60 Fibonacci number and store it in an array and use that array values for further calculations.

Link: Program to find last digit of n’th Fibonnaci Number

*/


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

#define sf scanf
#define pf printf

LL f[65] = {0};

LL fib(LL n)
{
    f[0] = 0;
    f[1] = 1;

    for (LL i = 2; i <= n; i++)
    {
        f[i] = (f[i-1] + f[i-2])%10;
    }

    return f[n];
}

LL findLastDigit(LL n)
{
    fib(60);

    return f[n%60];
}

int main()
{
    int t , tc=0;
    LL n;
    sf("%d", &t);
    while(t--)
    {
        memset(f , 0 , sizeof f);

        sf("%lld", &n);

        pf("Case %d: %lld is the last digit.\n", ++tc, findLastDigit(n));
    }

    return 0;
}

ACM ICPC Preliminary 2016 Team Practice Contest A.Multiplication Queries

Problem Link: A - Multiplication Queries 

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long
#define high 50005

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

LL ar[high], br[high];
LL tree[high * 3] , m;

LL multiple(LL a, LL b , LL c)
{
    if(!b) return 0;

    LL x = multiple(a , b/2, c)%c;

    if(!(b&1))
    {
        return ((x%c) + (x%c))%c;
    }

    else
    {
        return ((a%c) + (x%c)+(x%c))%c;
    }
}

LL bigmod(LL a, LL b , LL c)
{
    if(!b) return 1;

    LL x = bigmod(a , b/2, c)%c;

    if(!(b&1))
    {
        return multiple(x , x , c);
    }

    else
    {
        return (multiple(a%c, multiple(x , x , c)%c , c))%c;
    }
}

void build(LL node, LL b , LL e)
{
    if(b == e)
    {
        tree[node] = br[b];
        return;
    }

    LL Left = node * 2;
    LL Right = (node * 2)+1;
    LL mid = (b + e) / 2;

    build(Left , b , mid);
    build(Right, mid+1, e);

    tree[node] = (tree[Left]%m * tree[Right]%m)%m;
}

LL query(LL node, LL b , LL e, LL i, LL j)
{
    if(i > e or j < b) return 1;

    if(b >= i and e <= j)
    {
        //cout << tree[node] << "; ";
        return tree[node];
    }

    LL Left = node * 2;
    LL Right = (node * 2) + 1;
    LL mid = (b + e) / 2;

    LL pek = query(Left, b , mid, i , j);
    LL pdui = query(Right, mid+1, e , i , j);

    //cout << pek << " " << pdui << "; ";

    return (pek%m * pdui%m)%m;
}

int main()
{
    fast;
    int t , tc=0;
    LL n , q , k , i , l , r, tmp=1 , p;
    //cin >> t;
    sf("%d", &t);
    while(t--)
    {
        //cin >> n >> q >> k >> m;
        //ans.clear();
        sf("%lld %lld %lld %lld", &n, &q, &k ,&m);

        for(i=1; i<=n; i++)
        {
            //cin >> ar[i];
            sf("%lld", &ar[i]);
        }

        br[0] = 1;

        for(i=1; i<=n; i++)
        {
            br[i] = bigmod(ar[i] , k , m);

            //br[i]= (br[i]%m * br[i-1]%m)%m;
        }

        build(1 , 1 , n);

        //for(i=1; i<=n; i++) cerr << tree[i] << " ";

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf("%lld %lld", &l, &r);

            LL ans = query(1, 1, n, l , r);
            pf("%lld\n", ans%m);
        }

      }

    return 0;
}
 

LightOJ ACM ICPC Preliminary 2016 Team Practice Contest G. Chocolates

Problem Link: G.Chocolates


//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

vll v;

int main()
{
    int t;
    LL k , m , n , i , sum=0 , x , ans=0 , tmp;
    sf("%d", &t);
    while(t--)
    {
        v.clear();

        sf("%lld %lld %lld", &k, &m , &n);

        for(i=0; i<k; i++)
        {
            sf("%lld", &x);
            v.push_back(x);
        }

        sort(v.rbegin(), v.rend()); //for(i=0; i<k; i++) cerr << v[i] << " ";

        sum = ans = 1;

        for(i=1; i<k; i++)
        {
            if(v[i-1] == v[i])
            {
                ans+=sum;
            }

            else
            {
                sum+=(m * (v[i-1] - v[i]));
                ans+=sum;
            }
        }

        //cerr << ans << "\n";

        if(ans > n)
        {
            pf("impossible\n");
        }

        else
        {
            tmp = (n - ans) / k;

            pf("%lld\n", (tmp * k) + ans);
        }
    }

    return 0;
}

Extended Euclid

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int>pii;

pii EGCD(int a, int b)
{
    if(!b)
    {
        return pii(1, 0);
    }

    else
    {
        pii d = EGCD(b, a%b);

        return pii(d.second, d.first - (a / b) * d.second);
    }
}

int main()
{
    int a, b;

    while(cin >> a >> b)
    {
        pii ans = EGCD(a,b);

        cout << ans.first << " " << ans.second << "\n";
    }

    return 0;
}

Binary Search Lower Bound and Upper Bound

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

int ar[N+5];

int lowerBound(int itm , int sz)
{
    int lo=0, hi=sz-1 , mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2 ;

        if(ar[mid] == itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1 ;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int upperBound(int itm, int sz)
{
    int lo=0, hi=sz-1, mid;

    while(lo <= hi)
    {
        mid = (lo+hi) / 2;

        if(ar[mid] == itm)
        {
            lo = mid+1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int main()
{
    int n;

    cout << "Take array size: ";

    while(cin >> n)
    {
        int i;

        for(i=0;i<n;i++)
        {
            cin >> ar[i];
        }

        int q;
        cout << "Number of Query: ";
        cin >> q;

        while(q--)
        {
            int x;
            cin >> x;

            int lw,up;

            lw = lowerBound(x,n);

            cout << "index = " << lw << " value = " << ar[lw] << "\n";

            up = upperBound(x, n);

            cout << "index = " << up << " value = " << ar[up] << "\n";
        }

        cout << "Take array size: ";
    }

    return 0;
}

Upcomming_Eid_Ul_AZHA_Programmming_Contest Problem B. Even Digits

Link: Problem B - Even Digits Problem Link
AC Code Link: Problem B - Even Digits AC Code Link

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define high 10000

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int main()
{
    fast;
    int t, tc=0;
    LL n, quotiant=0;
    string ans="";
    cin >> t;
    while(t--)
    {
        ans="";
        cin >> n;

        cout << "Case " << ++tc << ": ";

        if(n==1)
        {
            outn("0");
            continue;
        }

        quotiant = n-1;

        while(quotiant > 0)
        {
            ans+=((quotiant % 5) * 2) + 48;

            quotiant = quotiant / 5;
        }

        reverse(ans.begin(), ans.end());
        outn(ans);
    }

    return 0;
}

Machine Learning

মেশিন লার্নিং এ বড় ধরণের একটা সাফল্য দশটা মাইক্রোসফট এর সমান হবে। এটা আমার কথা না, বিল গেটস নিজের কথা।
কম্পিউটার সাইন্স এর দারুণ একটা সাবজেক্ট হচ্ছে মেশিন লার্নিং। সাধারণত আমরা কম্পিউটারকে কিছু ইন্সট্রাকশন দেই, কম্পিউটার সে অনুযায়ী কাজ করে। কিন্তু মেশিং লার্নিং এর ক্ষেত্রে আমরা কিছু প্রসেস বলে দেই, বাকিটা সে নিজে নিজে শিখে নেয় এবং সে অনুযায়ী কাজ করে। যেমন আবহাওয়ার কথাই ধরা যাক, আমরা একটা কম্পিউটার প্রোগ্রামকে পূর্বের সকল আবহাওয়ার ডেটা দিব। ঐ ডেটা এনালাইসিস করে আমাদের প্রোগ্রাম আবহাওয়ার পূর্বাবাস জানাবে। আমরা এখানে বলে দিচ্ছি না কি জানাতে হবে। প্রোগ্রাম আগের ডেটা এনালাইসিস করে বর্তমান আবহাওয়া দেখে আমাদের বলে দিচ্ছে আগামীকালকের আবহাওয়া কেমন হতে পারে। এটাই মেশিং লার্নিং।
কম্পিউটার প্রোগ্রামকে ডেটা দিলেই তা এনালাইসিস করতে পারবে না। আমাদের কিছু ইন্সট্রাকশন দিয়ে দিতে হবে কিভাবে ডেটা এনালাইসিস করতে হবে। কি কি অ্যালগরিদম কিভাবে ব্যবহার করতে হবে, ইত্যাদি। এসব করে দিলে বাকি কাজ মেশিন বা প্রোগ্রাম নিজে করবে। এখন ছোট খাটো অ্যাপেও মেশিন লার্নিং এর দরকার হয়। ডেটা মাইনিং, ন্যাচারাল ল্যাঙ্গুয়েজ প্রসেসিং, ইমেজ রিকগনিশন, এক্সপার্ট সিস্টেম সহ কম্পিউটার সাইন্স এবং আর্টিফিশিয়াল ইন্টীলিজেন্স এর অনেক জায়গায় মেশিন লার্নিং এর প্রয়োগ হয়।
অনেক গুলো উদাহরণ দেওয়া যাবে। হাতের কাছের একটা উদাহরণ দেই। Madviser নামে একটা অ্যান্ড্রয়েড অ্যাপ রয়েছে। এটার কাজ হচ্ছে আপনার জন্য কোন মোবাইল প্যাকেজ ভালো হবে, তা সাজেস্ট করা। আর তার জন্য এটি আপনার সকল ডেটা প্যাকেজ এবং ভয়েস কল এনালাইসিস করে। এই অ্যাপকে সরাসরি কি করতে হবে, তা বলে দেওয়া হয় নি। কিছু ডেটা দেওয়া হচ্ছে, ঐ ডেটা এনালাইসিস করে ব্যবহারকারীকে একটা প্যাকেজ সাজেস্ট করছে। এটাও মেশিং লার্নিং এর একটা প্রয়োগ। অ্যাপটা বাংলাদেশী ডেভেলপারদের তৈরি।
আরেকটা সিম্পল উদাহরণ হচ্ছে OCR বা Optical Charecter Recognition/Reader. ছবি থেকে লেখা গুলো পড়ার জন্য ব্যবহৃত হয়। আমরা অনেকে ব্যবহার করেছি হয়তো। এটিও মেশিং লার্নিং এর একটি প্রয়োগ। ইমেজ থেকে ক্যারেকটার গুলো দেখে তারপর কোনটা কি, তা ডিটেক্ট করে। আর এই মেশিং লার্নিং এ ব্যবহৃত হয় Classification Algorithm. ইমেলে আসা কোনটা স্প্যাম, কোনটা স্প্যাম না, তা বের করতেও মেশিন লার্নিং বা ক্লাসিফিকেশন অ্যালগরিদম ব্যবহৃত হয়। এরকম অনেক গুলো অ্যালগরিদম এর ব্যবহার মিলেই হচ্ছে মেশিং লার্নিং।
মেশিন লার্নিং অ্যালগরিদম গুলোকে প্রধানত দুই ক্যাটেগরিতে ভাগ করা যায়।
- Supervised Learning.
- Unsupervised learning.
Supervised Learning: কিছু প্রি ডিফাইন ডেটাসেট এর উপর প্রোগ্রামকে ট্রেইন করা হয়। ঐ ট্রেইন ডেটা এর উপর ভিত্তি করে প্রোগ্রাম ডিসিশন দেয়। এটা হচ্ছে সুপারভাইসড লার্নিং। যেমন মেইলটি কি স্প্যাম না কি স্প্যাম না, এই ডিসিশনটা আগের কিছু ডেটার উপর নির্ভর করে দেয়া হয়। এটা হচ্ছে সুপারভাইসড লার্নিং এর উদাহরণ।
Unsupervised learning: আনসুপারভাইসড লার্নিং এ প্রোগ্রামকে কিছু ডেটা দেওয়া হয়। প্রোগ্রাম ঐ ডেটার উপর নির্ভর করে ডিসিশন দেয়। যেমন এক ঝুড়ি ফল রয়েছে। প্রোগ্রাম ভিন্ন ভিন্ন ফল কে ভিন্ন ভিন্ন ক্যাটেগরিতে ভাগ করবে, এটা হচ্ছে আনসুপারভাইড লার্নিং এর উদাহরণ।
সিরি, কর্টনা এসব হচ্ছে মেশিং লার্নিং এর সফল প্রয়োগ। ফেসবুকে ইমেজ আপলোড করার পর অটোমেটিকেলি কার ছবি, তা ডিটেক্ট করে। এটাও মেশিন লার্নিং এর প্রয়োগ। বিল গেটস মিথ্যে বলে নি। মেশিন লার্নিং কে যদি আরো ইফিশিয়েন্টলি প্রয়োগ করা যায়, তাহলে আমাদের পুরো প্রযুক্তি দুনিয়াটাই পাল্টে যাবে। এমন না যে চেষ্টা করা হচ্ছে না। নিয়মিতই এই সেক্টরটি ডেভেলপ হচ্ছে।
দুই ধরনের মানুষ রয়েছে। Watcher & Player. আপনি কোন ধরণের হবেন? Player হলে এখন থেকেই এসব নিয়ে পড়ালেখা করতে পারেন। জানতে পারেন আস্তে আস্তে। ইন্টারনেটে প্রচুর রিসোর্স রয়েছে। মেশিন লার্নিং এর উপর এই কোর্স দুইটি দারুণ এবং জনপ্রিয়।
coursearemachinelearning
udacitymachinelearning
গুগলে একটু সার্চ করলেই দারুণ সব রিসোর্স পাওয়া যাবে। ML এক্সপার্ট এর অনেক চাহিদা রয়েছে। আর আমাদের দেশে রয়েছে অভাব। যেখানে অভাব, সেখানেই সুযোগ। কাজে লাগানো আপনার ইচ্ছে  :) :)

Upcomming_Eid_Ul_AZHA_Programmming_Contest A. Helping Tool

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<map>
//#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf

typedef long long LL;
typedef long L;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef map<char, int> mpcii;
typedef map<char , bool> mpcb;
typedef vector<char>vc;

int main()
{
    fast;
    string s;
    //mpcii mp;
    //mpcb mpc;
    vc v;
    while(cin >> s)
    {
        //mp.clear();
        //mpc.clear();
        v.clear();

        int len = s.length() , i=0;

        //int x = 200000; cout << x;

       for(i=0; i<len; i++)
       {
           v.push_back(s[i]);
       }

       i=0;

       len=v.size(); //cout << "len1 = " << len << "\n";

       for(; i<len-1; i++)
       {
           if(v[i] == v[i+1])
           {
               int j = i;

               len-=2;

               for(; j<len; j++)
               {
                   v[j] = v[j+2];
               }

//               if(!mpc[v[i]] and !mpc[v[i+1]])
//               {
//                   mpc[s[i]] = true;
//                   mpc[s[i+1]] = true;
//               }

               //for(int k=0; k<v.size()-2; k++) cout << v[k] << " ";
               //cout << "\n";

               i=-1;
           }
       } //cout << "len = " << len << "\n";

       if(len <= 0) cout << "-1";

       else
       {
           for(i=0 ; i<len; i++) cout << v[i];
       }

       cout << "\n";
    }

    return 0;
}

// xraccabccbry

Cube Root - Binary Search - Bisection Method

// Cube root
// Binary Search-Bisection Method

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

#define out(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define ex 1e-6

typedef long long LL;

double diff(double n, double mid)
{
    if(n > (mid * mid *mid)) return n - (mid * mid *mid);
    else return (mid * mid *mid) - n;
}

double bisection(double n)
{
    double lo=0.0, hi=n, mid=0.0;

    while(true)
    {
        mid = (lo + hi) / 2.0;

        double d = diff(n,mid);

        if(d <= ex) return mid;

        if((mid * mid * mid) > n) hi = mid;
        else lo = mid;
    }
}

int main()
{
    double x;
    while(cin >> x)
    {
        cout << "Cube root of " << x << " is " << bisection(x) << "\n";
    }

    return 0;
}

Find the power by O(lgn)

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

#define out(x) cout << x << "\n"

// O(n) solution

//int power(int x, int y)
//{
//    if(y == 0) return 1;
//
//    if(y % 2 == 0)
//    {
//        int r = power(x, y/2);
//        return r*r;
//    }
//
//    else
//    {
//        return x * power(x, y/2) * power(x, y/2);
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgN) Solution

// when y is positive
// the function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

//int power(int x, int y)
//{
//    int temp;
//
//    if(y == 0) return 1;
//
//    temp = power(x, y/2);
//
//    if(y % 2 == 0) return temp * temp;
//
//    else
//    {
//        return x * temp * temp;
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgn), when y is negative

float power(int x, int y)
{
    float temp=0.0;

    if(y == 0) return 1;

    temp = power(x, y/2);

    if(y % 2 == 0) return temp * temp;

    else
    {
        if(y > 0) return x * temp * temp;

        else
        {
            return temp * temp / x;
        }
    }
}

int main()
{
    int x,y;

    while(cin >> x >> y)
    {
        cout << power(x, y) << "\n";
    }
}

Longest Decreasing Subsequence

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

const int inf = 9999;

int n, seq[100], ldsseq[100], I[100], L[100];

int BINARY_SEARCH(int lo, int hi, int itm)
{
    int mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(I[mid] < itm)
        {
            lo = mid + 1;
        }

        else
        {
            hi = mid - 1;
        }
    }

    return lo;
}

int LIS()
{
    int i, j , len=0 , r , Llen=0;

    for(i=0; i<n; i++)
    {
        r = BINARY_SEARCH(0, len, seq[i]);

        I[r] = seq[i];
        L[Llen++] = r;

        if(len < r)
        {
            len = r;
        }
    }

    //cout << "LDS Length: " << len;
    return len;
}

void find_squence( int mxlen)
{
    int i=0 , j;

    for(j=1; j<n; j++)
    {
        if(L[j] > L[i])
        {
            i = j;
        }
    }

    int top = L[i];

    top--;

    ldsseq[top] = seq[i];

    for(j=i-1; j>=0; j--)
    {
        if(seq[j] < seq[i] and L[j] == L[i]-1)
        {
            i=j;

            top--;

            ldsseq[top] = seq[i];
        }
    }

    cout << "Sequence: ";
    for(i=mxlen-1; i>=0; i--)
    {
        cout << ldsseq[i] << " ";
    }
}

int main()
{
    while(cin >> n)
    {
        int ilen=0;

        I[ilen++] = -inf;

        for(int i=0; i<n; i++)
        {
            cin >> seq[i];

            I[ilen++] = seq[i];
        }

        reverse(seq, seq+n);

        int rlen = LIS();

        find_squence(rlen);

        cout << "LDS Length = " << rlen << "\n";
    }

    return 0;
}

Longest Increasing Subsequence with O(N log K)

// LIS -- O(N log K)

#include<bits/stdc++.h>
#define sze 100

using namespace std;

const int inf=9999;

int seq[sze+5], lisseq[sze+5] , n , I[sze+5], L[sze+5];

int Binary_Search(int lo, int hi, int itm)
{
    int mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(I[mid] < itm)
        {
            lo = mid+1;
        }

        else
        {
            hi = mid-1;
        }
    }

    return lo;
}

int LIS()
{
    //memset(L, 1, sizeof(L));

    int i , r , len=0 , llen=0;

    for(i=0; i<n; i++)
    {
        r = Binary_Search(0, len, seq[i]);

        I[r] = seq[i];
        L[llen++] = r;

        if(len < r)
        {
            len = r;
        }
    }

    return len;
}

void find_sequence(int mxlen)
{
    int i=0 , j;

    for(j=1; j<n; j++)
    {
        if(L[i] < L[j])
        {
            i = j;
        }
    }

    int top = L[i];

    top--;

    lisseq[top] = seq[i];

    for(j=i-1; j>=0; j--)
    {
        if(seq[j] < seq[i] and L[j] == L[i] - 1)
        {
            i = j;

            top--;

            lisseq[top] = seq[i];
        }
    }

    cout << "LIS Sequence: ";

    for(i=0; i<mxlen; i++)
    {
        cout << lisseq[i] << " ";
    }
}

int main()
{
    while(cin >> n)
    {
        int ilen=0;

         I[ilen++] = -inf;

        for(int i=0;i<n;i++)
        {
            cin >> seq[i];

            I[ilen++] = seq[i];
        }

        int lislen = LIS();

        find_sequence(lislen);

        cout << "LIS Length: " << lislen << "\n";
    }

    return 0;
}

Find Total Number of Distinct Prime Factors

#include<bits/stdc++.h>

#define limit 100100

using namespace std;

typedef long long LL;
typedef bitset<limit>bs;

int distinctfactors[limit] = {0};

bs bit;

void distinct_Prime_factors()
{
    LL i,j;

    bit.set();
    bit[0] = bit[1] = 0;

    for(i=2; i<limit; i++)
    {
        if(bit[i])
        {
            for(j=i*2; j<limit; j+=i)
            {
                if(!(j % i))
                {
                    distinctfactors[j]+=1;
                }

                bit[j] = 0;
            }
        }
    }
    //for(i=2;i<10;i++)cout<<distinctfactors[i]<<" ";
}

int main()
{
    distinct_Prime_factors();
    cout << "Enter a number to find total distinct prime factor: ";
    int n;
    while(cin >> n)
    {
        cout << "Total Distinct Prime Factor = " << distinctfactors[n] << "\n";

        cout << "Enter a number to find total distinct prime factor: ";
    }

    return 0;
}

Find The Total Number of Prime Factors of a number

#include<bits/stdc++.h>

#define limit 100100

using namespace std;

typedef long long LL;
typedef bitset<limit>bs;

int totalfactors[limit];

bs bit;

void find_total_factors()
{
    LL i,j;
    bit.set();
    bit[0] = bit[1] = 0;

    for(i=2; i<limit; i++)
    {
        if(bit[i])
        {
            totalfactors[i] = 1;

            for(j=i*2; j<limit; j+=i)
            {
                totalfactors[j] = 1 + totalfactors[j / i];

                bit[j] = 0;
            }
        }
    }
}

int main()
{
    find_total_factors();
    cout<<"Enter number to find total factors of that number: ";
    int number;
    while(cin >> number)
    {
        cout<<"Total Factors of " << number << " is = " << totalfactors[number] << "\n";

        cout<<"Enter number to find total factors of that number: ";
    }

    return 0;
}

Big Integer Sum between Two Numbers

#include<bits/stdc++.h>

using namespace std;

void x_y(string a, string b)
{
    int alen=a.size(), blen=b.size(),i,j, sum, carry=0, num[1009], numlen=0;

    i=alen-1;
    j=blen-1;

    for(; i>=0; i--)
    {
        sum = a[i]-48;

        if(j>=0)
        {
            sum+=(b[j]-48);
            j--;
        }

        sum+=carry;

        if(sum > 10)
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }
        else
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        numlen++;
    }

//    if(carry)
//    {
//        cout << carry;
//    }

    if(carry)
    {
        num[numlen++]=carry;
    }

    for(i=numlen-1; i>=0; i--)
    {
        cout << num[i];
    }

    cout << endl;
}

void eql(string a, string b)
{
    int alen=a.size(), blen=b.size(), i, j, sum, carry=0, num[1009], numlen=0;

    i=alen-1;
    j=blen-1;

    for(; i>=0 and j>=0; i--,j--)
    {
        sum = (a[i]-48) + (b[j]-48);

        sum+=carry;

        if(sum > 10)
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        else
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        numlen++;
    }

    if(carry)
    {
        cout << carry;
    }

    for(i=numlen-1; i>=0; i--)
    {
        cout << num[i];
    }

    cout << endl;
}

int main()
{
    string x,y;

    while(cin >> x >> y)
    {
        if(y.size() > x.size())
        {
            swap(x,y);
        }

        if(x.size() > y.size())
        {
            x_y(x,y);
        }

        else
        {
            eql(x,y);
        }
    }

    return 0;
}

sscanf/sprintf (stdio.h/cstdio)

#include<bits/stdc++.h>

using namespace std;

#define pf printf

int main()
{
    //cout << "hello";

    char ch[20];
    gets(ch);

    int cid;
    char name[100];
    int solved;

    sscanf(ch, "%d %s %d", &cid,&name,&solved); // String theke data read korar jonno

    pf("%d %s %d\n",cid,name,solved);

    int n=1001;
    char cr[10];

    sprintf(cr, "%d", n); // kono kichuke Char e convert korte
    pf("%s",cr);

    return 0;
}

Number of Divisors/factors (DP Approach)

for only Prime Factors 

int num[mx7+9];

void nof()
{
    int i,j;

    for(i=4;i<=mx7;i+=2)
    {
        num[i] = 2;
    }

    for(i=3;i*i<=mx7;i+=2)
    {
        if(!num[i])
        {
            for(j=i*i;j<=mx7;j+=i)
            {
                num[j] = i;
            }
        }
    }

    for(i=2;i<=mx7;i++)
    {
        int n = num[i] ? num[i] : i;
        num[i] = 1 + num[i/n];
    }

    for(i=2;i<=21;i++)cp(num[i]);
}

int main()
{
    nof();
} 

Is n a Perfect Square ?

// Header file begin
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<cmath>
#include<cctype>
#include<sstream>
#include<set>
#include<list>
#include<stack>
#include<utility>
#include<queue>
#include<algorithm>
#include<cstdlib>
// End
//..........
// Macro
#define sf scanf
#define pf printf
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define mem(c,v) memset(c,v,sizeof(c))
#define cp(a) cout<<" "<<a<<" "
#define nl puts("")
#define sq(x) ((x)*(x))
#define all(x) x.begin(),x.end()
#define reall(x) x.rbegin(),x.rend()
#define s_wap(x,y) x^=y;y^=x;x^=y;
#define sz size()
#define gc getchar()
#define pb push_back
#define freader freopen("input.txt","r",stdin)
// End.........

// Size
#define mx7 20000100
#define mx6 1500000
#define mx5 100005
#define mx4 1000100
#define inf 1<<30                                           //infinity value
#define eps 1e-9
#define mx (65540)
#define mod 1000000007
#define pi acos(-1.0)

// Macros for Graph

#define white 1
#define gray 2
#define black 3
#define nil 0

using namespace std;
/***************/

// typedef

typedef long long LL;
typedef long L;
typedef unsigned long long ull;
typedef unsigned long ul;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int>vi;
typedef vector<long long> vll;
typedef vector<long>vl;
typedef vector<char>vch;
typedef vector<string>vs;
typedef map<int,int>mpii;
typedef map<int,bool>mpbi;
typedef map<long,bool>mpbl;
typedef map<long long,bool>mpbll;
typedef map<char,int>mpci;
typedef map<char,bool>mpbc;
typedef map<string,int>mpsi;
typedef map<long long,long long>mpll;

// template

template<class T> T gcd(T a, T b ) {return b!=0?gcd<T>(b,a%b):a;}
template<class T> T large(T a, T b ) {return a>b?a:b;}
template<class T> T small(T a, T b ) {return a<b?a:b;}
template<class T> T diffrnce(T a, T b) {return a-b<0?b-a:a-b;}

int prime[(mx>>6)+1],prm[(mx>>1)+9],plen=0,qrt=(int)sqrt(double(mx));

#define setbit(n) (prime[n>>6] |= (1<<((n>>1)&31)))
#define checkbit(n) (prime[n>>6] & (1<<((n>>1)&31)))

void sieve()
{
    int i,j;
    for(i=3;i<=qrt;i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i;j<=mx;j+=i+i)
            {
                setbit(j);
            }
        }
    }
    prm[plen++]=2;
    for(i=3;i<=mx;i+=2)
    {
        if(!checkbit(i))
        {
            prm[plen++]=i;
        }
    }
    //lp1(i,100)cp(prm[i]);
}

mpii mp;

void factors(int n)
{
    mp.clear();
    int i,keep=n;
    bool yes1=false,yes2=false;
    for(i=0;i<plen and sq(prm[i])<=n;i++)
    {
        if(!(n%prm[i]))
        {
            while(!(n%prm[i]))
            {
                mp[prm[i]]++;
                n/=prm[i];
                if(n==0 or n==1)break;
            }

            if(!(mp[prm[i]]&1))
            {
                yes1=true;
            }
        }
    }

    if(n>1)
    {
        mp[n]++;
    }
    if(!(mp[n]&1))
    {
        yes2=true;
    }
    if(yes1)
    {
        if(yes2)
        {
            cout<<"Yes: " << keep << " is a perfect square\n";
        }
        else
        {
            cout<<"No: " << keep << " is not a perfect square\n";;
        }
    }
    else
    {
        cout<<"No: " << keep << " is not a perfect square\n";
    }
}

int main()
{
    sieve();
    int n;
    while(cin >> n)
    {
        if(n==1)
        {
            cout<<"Yes: " << n << " is a perfect square\n";
            continue;
        }

        factors(n);
    }

    return 0;
}

Uva and LightOJ (Easy) Problem List

Uva 11526 - H(n)

Analysis

According to the given code :: 

 long long H(int n){
long long res = 0;
for( int i = 1; i <= n; i=i+1 ){
res = (res + n/i);
}
return res;
}

We can get for n=20 is ::
20+10+6+5+4+3+2+2+2+2+1+1+1+1+1+1+1+1+1+1
=  20+10+6+5+4+3+8+10
=  20+10+6+5+10+8+4+3
=  20+10+6+5+1*(20-10)+2*(10-6)+3*(6-5)+4*(5-4)
=  20+10+6+5+20-10+20-12+18-15+20-16
=  20+10+6+5+20+10+6+5-16
= (20+10+6+5)+(20+10+6+5)-4*4
= 2(20+10+6+5) - 4*4

again, sqrt(20) = 4;

So, see that ...