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;
}

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;
}

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;
}

Summation of Divisors

Explanation ::

Thanks to Jane Alam Jan (founder of LightOj)

Code:: goes to Below :::

 /// 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>
/// End
//..........
/// Macro
#define sf scanf
#define pf printf
#define sfint(a) scanf("%d",&a)
#define sfl(a,b) scanf("%ld %ld",&a,&b)
#define sfll(a,b) scanf("%lld %lld",&a,&b)
#define sfd(a,b) scanf("%lf %lf",&a,&b)
#define sff(a,b) scanf("%f %f",&a,&b)
#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 sz size()
#define gc getchar()
#define pb push_back
/// 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 0
#define gray 1
#define black -1
#define nil -2

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<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?a:gcd(b,a%b);}
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;}


using namespace std;
//..................................................................................................................
template<class T> T setbit(T n, T pos){n=n|(1<<pos); return n;}
template<class T> T checkbit(T n, T pos){n=n&(1<<pos); return n;}

int prime[1],pr[100],plen=0;

void seieve(int n)
{
    int i,j,x=sqrt(n);

    prime[0]=setbit(prime[0],0);
    prime[0]=setbit(prime[0],1);

    for(i=4;i<=n;i+=2)prime[i>>5]=setbit(prime[i>>5],i&31);

    for(i=3;i<=x;i+=2)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            for(j=i*i;j<=n;j+=i)
            {
                prime[j>>5]=setbit(prime[j>>5],j&31);
            }
        }
    }

    for(i=2;i<=n;i++)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            pr[plen++]=i;
        }
    }
}

mpii mp;

void divisor(int n)
{
    int i,m=1,tmp,take=n;

    mp.clear();

    for(i=0;i<plen and sq(pr[i])<=n;i++)
    {
        if(!(n%pr[i]))
        {
            while(!(n%pr[i]))
            {
                mp[pr[i]]++;
                n/=pr[i];
                if(n==0 or n==1) break;
            }

            tmp=powl(pr[i],(mp[pr[i]] + 1));
            m*=((tmp-1)/(pr[i] - 1));
        }
    }

    if(n>1)
    {
        tmp=powl(n,2);
        m*=((tmp-1) / (n-1));
    }

    pf("Summation of the divisors of %d is %d :)\n",take,m);
    m=1;
}

int main()
{
    int n;
    seieve(100);

    cout << "Enter Number(up to 100) : ";

    while(sfint(n)==1)
    {
         divisor(n);

         cout << endl << "Enter Number(up to 100) : ";
    }

    return 0;
}

//================================================================================================================
/*

                                         Summation of Divisors
                                         =====================

Let the divisors of 60 = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60; Total=12;

So, the total Summation of that divisors is = 1+2+3+4+5+6+10+12+15+20+30+60 = 168;

Formula::
==========

( r ^ ( n + 1 ) - 1 ) / ( r - 1 );

**** r = prime factorization of that number. n = power of the prime factorization.

So, for 60 = 2^2 * 3^1 * 5^1 ;

r=2,3,5;

n=2,1,1;

result = ( ( 2 ^ ( 2 + 1 ) ) - 1 ) / (2-1) * ( ( 3 ^ ( 1 + 1 ) ) - 1 ) / (3-1) * ( ( 5 ^ ( 1 + 1 ) ) - 1 ) / (5-1);

=> result = 7 * 4 * 6 = 168 ;

so, result = 168;

*** In which function that we get the summation of divisor is called Sigma function ;)
*/

Find the Way to express a number by Consecutive Sum of integers

একদম সোজা ।
কোন একটা নাম্বার কে কত ভাবে ধারাবাহিক নাম্বারের যোগফল দ্বারা বের করা যায় তা জানতে হলে আগে ওই নাম্বারের প্রাইম ফেক্টোরাইজেশন করতে হবে পরে আমরা সেখান থেকে বেজোড় প্রাইম ফেক্টর গুলুর পাওয়ারের যোগ করলেই বলতে পারব ।

যেমন ১২ এর প্রাইম ফেক্টর গুলু হচ্ছে, ১২=২*২*৩;
এখানে বেজোড় প্রাইম ফেক্টর  কেবল ৩, যার পাওয়ার ১;
সুতরাং , আমাদের Way হচ্ছে = ১+০ = ১;

কিন্তু কথা হচ্ছে, যেহেতু সকল নাম্বারের একটা কমন ডিভিজর হল ১ এবং সেইসাথে যেহেতু ১ একটি বেজোড় নাম্বার, সেহেতু আমরা আমাদের আগের প্রাপ্ত মানের সাথে ১ যোগ করে দেব । 

So, the Way is = ১+(১) = ২;

আবার, ৯=৩^১*৩^১;
সুতরাং হবার কথা ১+১=২;
যেহেতু ১ সকল নাম্বারের ডিভিজর এবং বেজোড় নাম্বার সো Way হবে = ২+ (১) = ৩;

এবার কোডটা নিজে নিজে করে ফেলুন । আমি যদি প্রাইম নাম্বার কিংবা প্রাইম ফেক্টর বের করতে জানেন তাহলে এর কোড করা আপনার জন্য কোন ব্যাপার না ।

তবু নিচে কোডের লিঙ্ক টা দিয়ে দিলাম ... কোন প্রবলেমে না পড়া পর্যন্ত দেখবেন না আশা করি । 

( বিঃদ্রঃ আগে নিজে চেষ্টা করুন, না পারলে কোড দেখে এনালাইসিস করে নিজের মত করে করুন । কখনও কারো কোড কপি পেস্ট করে সাবমিট করবেন না । )

কোডের জন্যঃঃ  Uva 10290

Seieve of Eratosthenes

সিভ অফ এরাটোসথেনিসের ইফিসিয়েন্ট ভার্সনঃ

 বিটওয়াইজ সিভ 

প্রথমে কোডটা দেখা যাকঃ 

---

কোডঃ

 

// bitwise Seieve of Eratosthenes
#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 <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 105
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

int prime[1];
// vagfol dibe. oi vagfoler soman index e giye index number er bit ke set korbe 
int setbit(int n, int pos)
{
    n = n | (1<<pos); // 1<<pos mane 2^pos
    return n;
}
// vagshesh dibe. oi vagshesh tomo bit ke check korbe
bool checkbit(int n, int pos)
{
    n = n & (1<<pos);
    return n;
}

void seieve(int n)
{
    int x=sqrt(n),i,j;

    prime[0]=setbit(prime[0],0); // initialize korlam 0 diye
    prime[0]=setbit(prime[0],1); // initialize korlam 1 diye

    for(i=4;i<=n;i+=2)
    {
        prime[i>>5] = setbit( prime[i>>5], i&31);
    }
// i>>5 mane i ke 32 diye vag kore vagfol. i&31 mane i ke 32 diye vag kore vagshesh
    for(i=3;i<=x;i+=2)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            for(j=i+i;j<=n;j+=i)
            {
                prime[j>>5]=setbit( prime[j>>5] , j&31 );
            }
        }
    }
}

int main()
{
    int n,i; cin >> n; int d=n;

    seieve(n);

    lp2(i,n)
    {
        if(!checkbit( prime[i>>5], i&31 ))
        {
            cout << i ;

            if(d>0) // space control kora hoise just.
            {
                cout << " ";
                d--;
            }
        }
    }

    nl;

    return 0;
} 

---

এই সিভের মাধ্যমে আমরা n পর্যন্ত সব গুলু নাম্বারের প্রাইম জেনারেইট করব । এজন্য আমরা একটি অ্যারে ডিক্লেয়ার করে দিলাম আগে । এই অ্যারের কাজ হচ্ছে সে প্রতিটি ইন্ডেক্সের প্রতিটি ইলিমেন্টের বিট গুলু কে ফ্ল্যাগিন (নির্দেশক) করবে ।
কি বুঝা যাচ্ছে না তো ??
আচ্ছা, আমরা জানি int হল ৩২ বিট মেমরির ডাটা টাইপ । এবং অ্যারের সাইজ হতে হবে [n+1] যা অ্যারের বেসিক কনসেপ্ট । এখন n এর মান যদি 5 হয় । তাহলে 0 থেকে 5 পর্যন্ত অ্যারেটি দেখতে এইরকম হবে ...

---

 
position                            ...8 7654 3210
prime[0] = 0000 0000 0000 0000 0000 0000 0001 0011 

---

তো এই যে প্রতি অ্যারের ১ টি বিট ছাড়া নাকি ৩১ টি বিট অব্যবহৃত থেকে যাচ্ছে তাঁর প্রতিটিকে আমরা  ফ্ল্যাগিন বা নির্দেশক করব ।
আর এতে করে আমরা ১টি অ্যারে ইলিমেন্টের মাধ্যমে ৩২ টি নাম্বার কে প্রকাশ করতে পারব । তাঁর মানে একই সাইজের অ্যারেতে আমরা আগের রেঞ্জের ৩২ গুন পর্যন্ত প্রাইম নাম্বার জেনারেইট করতে পারব । 
আর এতে করে prime[0] এর জন্য 0 থেকে 31 পর্যন্ত নাম্বার গুলুর ফ্ল্যাগ থাকবে । এবং দ্বিতীয় এলিমেন্ট বা prime[1] এ 32 থেকে 63 পর্যন্ত নাম্বারগুলোর ফ্ল্যাগ থাকবে, এভাবে চলতে থাকবে ...
এখন আমরা দেখব যে, setbit এবং checkbit কি কাজ করেঃ
সিভে লুপের মধ্যে যখন কোন নাম্বার আসবে তখন সেই নাম্বারটিকে 32 দিয়ে ভাগ করব ( বলে রাখি বিটওয়াজে ৩২ = ২^৫ লিখতে গেলে 1<< 5 এইভাবে লিখতে হয়। )। ভাগফল যত হবে তত নাম্বার ইন্ডেক্সে নাম্বারটির ফ্ল্যাগ আছে। এখন কোন বিটটি ফ্ল্যাগ হবে সেটির জন্য আমরা নাম্বারটিকে 32 দিয়ে mod করব ( বলে রাখি বিটওয়াজে a mod b করতে গেলে  a & (b-1) এইভাবে লিখতে হয়। ) । ভাগশেষ যেটি হবে সেটিই হল নাম্বারটির ফ্ল্যাগের পজিশন।
যেমনঃ
আমরা যদি 4 এর ফ্ল্যাগ সেট করতে চাই অথবা দেখতে চাই ফ্ল্যাগটি 1 নাকি 0 তাহলে prime অ্যারের 4/32 = 0 ইন্ডেক্সের এলিমেন্টে যাব এবং 4%32 = 4 নাম্বার বিটটি সেট করব বা চেক করব। একইভাবে যদি 32 এর জন্য করি তাহলে 32/32 = 1 ইন্ডেক্সের এলিমেন্টে যাব এবং 32%32 = 0 নাম্বার বিটটি চেক করব। এভাবে করে আমরা যেকোন নাম্বারের জন্য কাজটি করতে পারি।
তো আসলে এই কাজ গুলুই করে setbit এবং checkbit । আরো ক্লিয়ারলি বললে setbit n এর পজিশন তম বিট কে সেট করবে এবং checkbit n এর পজিশন তম বিট কে চেক করবে সেটা কোন ফ্ল্যাগে আছে 0 নাকি 1 ।
তো, এইভাবে বিটওয়াইজ সিভ ব্যবহার করে আমরা আমাদের  প্রোগ্রাম কে আরো ইফিসিয়েন্ট এবং আরো ফাস্ট করে তুলতে পারি ।।

Euler's totient function

নাম্বার থিওরির খুব গুরুত্তপূর্ণ একটা টপিক হচ্ছে এই Euler's totient function. যা, বলা যায় অনেকটা না জানলেই না । আমি মনে করি এই ফাংশনের ক্রিয়া কর্ম না জানলে নাম্বার থিওরির বিশাল একটা পার্ট আপনার কাছে অজানাই থেকে যাবে । 

তাই এই নিয়ে কিছু বলব বলে ঠিক করেছি ... 

শুরুতে বলি ...

তখন সালটা ১৭৬৩ । লিওনার্দ অয়লার তখন সবে এই ফাংশন টা আবিস্কার করেছেন । কিন্তু দূর্ভাগ্যবশত তিনি কোন সিম্বল খুজে পাচ্ছিলেন না এটা প্রকাশ করার জন্য । 

১৭৮৪ সালে এক পাব্লিকেশনের উদ্দ্যেশ্যে তিনি এই বিষয়ে আবার স্ট্যাডি করেন এবং এটাকে প্রকাশ করার জন্য একটা গ্রিক সিম্বল ব্যবহার করেন যা দেখতে অনেকটা ' π ' এর মত । 

তখন তিনি সেটাকে πD হিসেবে প্রকাশ করেছিলেন যা বুঝাচ্ছে "the multitude of numbers less than D, and which have no common divisor with it".

এরপর ১৮০১ সালে গণিতবিদ গাউস Disquisitiones Arithmeticae তে একটি স্ট্যান্ডার্ড নোটেশনের মাধ্যমে অয়লারের এই ফাংশনটি ব্যবহার করেন, এবং সেই  স্ট্যান্ডার্ড নোটেশনটি ছিল φA (আমরা বলি phi of A) . তখন থেকেই এই ফাংশনটি Euler's phi function বা কেবল phi function নামে পরিচিতি লাভ করে । 

১৮৭৯  সালে  J. J. Sylvester এই ফাংশনে totient  কথাটি জুড়ে দেন । এরপর থেকেই এটি মূলত Euler's totient function বা  Euler totient বা কেবল Euler's totient হিসেবে আত্মপ্রকাশ করে ।

 Euler's totient function কি করে ... 

 নাম্বার থিওরিতে Euler's totient function কে φ(n) প্রকাশ করা হয় । যদি φ(n)=x হয়, তাঁর মানে 1 থেকে n পর্যন্ত x টি সংখ্যা আছে যাদের সাথে n এর gcd হচ্ছে 1 । 

যদি gcd(a,b)=1 হয়, আমরা বলি a আর b একে অপরের co-prime.

যেমন n=9 এর জন্য gcd(9,3)=gcd(9,6)=3  এবং  gcd(9,9)=9 । 

আর বাকি ৬ টি সংখ্যার ক্ষেত্রে  gcd(9,1)=gcd(9,2)=gcd(9,4)=gcd(9,5)=gcd(9,7)=gcd(9,8)=1 ... দেখা যাচ্ছে এখানে সবকটি নাম্বারের ক্ষেত্রে gcd=1 হচ্ছে এবং এমন নাম্বারের সংখ্যা ৬ টি । আর তাই φ(9)=6 ।

অয়লারের প্রোডাক্ট ফরমুলা অনুযায়ী  Euler's totient function কে এভাবে প্রকাশ করা যায়ঃঃ

φ(n)=n∏p|n(1−1p)

যেখানে p হচ্ছে প্রাইম নাম্বার । আর p|n হচ্ছে সেই সব প্রাইম নাম্বার যারা n কে নিঃশেষে ভাগ করতে পারে । [ তাঁর মানে n এর প্রাইম ফেক্টোরাইজেশন ]
যেমনঃ  a|b এর মানে হচ্ছে  a নিঃশেষে ভাগ করতে পারে b কে । যেখানে  a অবশ্যই একটা প্রাইম নাম্বার । তাঁর মানে a হচ্ছে  b এর ডিভিজর ।

---

একটা উদাহরণ দেখা যাকঃ 

 9 = 3 * 3 ; 

φ(9) = 9 * (1 - ( 1 / 3 ) ) = 9 * ( 2 / 3 ) = 6;

p = 3 ; যা  ৯ এর ডিভিজর ।

---

∏$$

এখন এই উদাহরণ থেকে এও স্পস্ট যে, ৯ এর relatively prime ৬ টি । তাঁর মানে  gcd(9,1)=gcd(9,2)=gcd(9,4)=gcd(9,5)=gcd(9,7)=gcd(9,8)=1। 
সুতরাং ৯ এর  Relatively Prime হচ্ছেঃ 1,2,4,5,7,8 । (উপরেই বলা ছিল)

Relatively Prime Number হচ্ছে যে যে নাম্বারের সাথে n এর gcd=1 ; 

---

আবার 120 এর ক্ষেত্রে, 120 =  2³ * 3¹ * 5¹
 φ(120) = 120 (1- (1/2)) * (1- (1/3)) * (1- (1/5)) = 32 ;

সুতরাং বুঝাই যাচ্ছে ১২০ এর Relatively Prime ৩২ টি ।
[বিঃদ্রঃ φ(n) = n * ( 1 - ( 1 / p ) ) =  n * n / p ও লিখা যায় । ( কোডে ইমপ্লিমেন্টেশন করা হয়েছে এইভাবে ) ]
RSA Encryption System এ Euler's totient function এর গুরুত্ব অনেক । 

---

সাধারণ ইমপ্লিমেন্টেশনঃঃ

 // Implements Euler Totient Function with Prime factorization
#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 <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define nl puts("")
#define MX 105
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

// generating Seieve of Erathosthenis

bool stats[MX]; vector<int> p; int plen;

void seieve()
{
    mem(stats,false);

    stats[0]=stats[1]=true;
    int i,j,qrt;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt=(int) sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!stats[i])
        {
            p.push_back(i);
        }
    }

    plen=p.size();
}

vector<int>primefactors; int prmfctorlen;

bool color[MX];

void primefacto(int n) // performing prime factorization
{
    int i,j;

    mem(color,false);

    for(i=0;i<plen and p[i]*p[i]<=n;i++)
    {
        if(!(n%p[i]))
        {
            while(!(n%p[i]))
            {
                if(!color[p[i]]) // same factor never come multiple time..
                {
                    primefactors.push_back(p[i]);
                }

                color[p[i]] = true;

                n/=p[i];

                if(n==0 or n==1) break;
            }
        }
    }

    if(n!=1)
    {
        primefactors.push_back(n);
    }

    prmfctorlen = primefactors.size();
}

int euler_phi(int n)
{
    primefacto(n);

    int i,phi=n;

    for(i=0;i<prmfctorlen;i++)
    {
        phi-=phi/primefactors[i];
    }

    return phi;
    //cout << phi;
}

int main()
{
    int i;
    seieve();
    //lp1(i,plen)cout << p[i] << " ";
    int n; cin >> n;
    //primefacto(n);
    //lp1(i,prmfctorlen) cout << primefactors[i] << " ";
    int res=euler_phi(n);
    cout << res << endl;

    return 0;
}

---

অপ্টিমাইজড ইমপ্লিমেন্টেশনঃঃ  

 // Euler Totient Function modified Code
#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 <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define nl puts("")
#define MX 1005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

// generating Seieve of Erathosthenis

bool stats[MX]; vector<int> p; int plen;

void seieve()
{
    mem(stats,false);
    int i,j,qrt;

    stats[0]=stats[1]=true;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt=(int)sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!stats[i])
        {
            p.push_back(i);
        }
    }

    plen=p.size();
}

int phi[MX+5];

void euler_phi()
{
    int p,k,i,j;

    for(i=1;i<=MX;i++) phi[i]=i; // initialize the phi array.

    for(p=2;p<=MX;p++)
    {
        if(!stats[p]) // check either p is prime or not.
        {
            if(phi[p]==p)
            {
                for(k=p;k<=MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int gcd (int a, int b)
{
    return (b==0 ? a : gcd(b,a%b));
}

int main()
{
    int i,j,n,p,k,sp,c;
    seieve();
    //lp1(i,plen) cout << p[i] << " ";
    euler_phi();

    while(cin >> n)
    {
        sp=0;

        cout << "Relatively Primes of " << n << " are : ( ";

        lp2(i,n)
        {
            if(gcd(n,i)==1) // finding relatively prime numbers
            {
                sp++; c=sp;

                cout << i;

                if(c>0)
                {
                    cout << " ";
                    c--;
                }
            }
        }

        cout << ")";

        cout << endl << "Total Number of Relatively Primes of " << n << " is ( " << phi[n] << " )" << endl;
    }

    return 0;
}

Euler Phi Sieve_Version

// Euler Phi Sieve version

#include<bits/stdc++.h>

#define SZ 100100

using namespace std;

int phi[SZ+9];

void generate_phi()
{
    int i,j;

    phi[1] = 1;

    for(i=2; i<SZ ; i++)
    {
        if(!phi[i])
        {
            phi[i] = i-1;

            for(j=i+i; j<SZ; j+=i)
            {
                if(!phi[j])
                {
                    phi[j] = j;
                }

                //phi[j] = phi[j] / i * (i-1) ;
                phi[j] = phi[j] / i;
                phi[j]*=(i-1);
            }
        }
    }
}

int main()
{
    generate_phi();

    for(int i=1;i<=10;i++)
    {
        cout << "for " << i << ".number of Co prime: " << phi[i];
        puts("");
    }

    return 0;
}
 

---

আশা করি কোড বুজতে কোন অসুবিধা হবে না এবং প্রবলেম সল্ভ করার পরামর্শ থাকল । আমি অবশ্য স্টার্ট করেছিলাম LightOJ 1007 - Mathematically Hard এই প্রবলেম দিয়ে । সব শেষে শুভকামনা রইল । আর হ্যাঁ, যেকোন ভুল ক্ষমার দৃষ্টিতে দেখবেন সেই সাথে কমেন্ট করতে কোন দ্বিধা করবেন না । 
Happy Coding...

---

Almost Prime Number's

                                       == Almost Prime Number ==

Almost Prime Number হচ্ছে সেই সকল প্রাইম নাম্বার যাদের প্রাইম ফেক্টোরিজেশন কেবলেই একটা প্রাইম নাম্বার ।
যেমনঃ
              ১-১০ পর্যন্ত Almost Prime Number ৩ টি ।
                ৪=২*২ ; ৮=২*২*২ ; ৯=৩*৩ ;
এখানে ৪,৮,৯ প্রতিটি সংখ্যার প্রাইম ফেক্টোরিজেশন কেবল একটা সংখ্যা । ৪ ও ৮ এর ক্ষেত্রে ২ এবং ৯ এর ক্ষেত্রে ৩ ।
আবার ১১-২০ পর্যন্ত Almost Prime Number ১ টি । তা হল ১৬=২*২*২*২ ; 
কিন্তু লক্ষ্য করুন, Almost Prime Number গুলুর একটি সংখ্যাও প্রাইম নাম্বার নয় । তো, সে ক্ষেত্রে আপনি যদি প্রতিটি প্রাইম নাম্বারের ২ থেকে ইনফিনিটি সংখ্যক পাওয়ারের কথা চিন্তা করেন দেখবেন আপনি আপনার Almost Prime Number গুলু পেয়ে গেছেন ।

২	৩	৫	৭	১১	১৩	১৭	১৯

ধরুন, আমার কাছে ১-২০ পর্যন্ত এই প্রাইম নাম্বার গুলু আছে ।এখন আমি প্রতিটি প্রাইমের যদি পাওয়ারের কথা চিন্তা করি (পাওয়ার > ১ ) ২০ এর আগ পর্যন্ত তাহলে কি আসে একবার দেখা যাকঃ
২ এর ক্ষেত্রে আমরা পাব - ৪(২*২); ৮(২*২*২); ১৬(২*২*২*২); ৩২(২*২*২*২*২) > ২০ 
৩ এর ক্ষেত্রে আমরা পাব - ৯(৩*৩) ; ২৭(৩*৩*৩) > ২০ 
৫ এর ক্ষেত্রে আমরা পাব - ২৫(৫*৫) > ২০... ... 
তো, ১-২০ পর্যন্ত আমরা Almost Prime পাব ( ৪,৮,৯ ও ১৬ ) মোট ৪ টি । 

এবার একটু নিচের কোডটি দেখা যাকঃ 

for(i=0;i<MX;i++)
    {
        if(!flag[i])
        {
            //for(j=p[i]*p[i];j<MX;j*=p[i]) almost.pb(j);

            for(j=i*i;j<1000000000005;j*=i)  // **** Take Care about that range ! i have got so much WA for that..
            {
                almost.pb(j);
            }
        }
    }

Where MX=1000005;  flag[0]=flag[1]=true;

আমরা আসলে পাওয়ারের কথা খাতা কলমে চিন্তা করে খুব সহজেই একটা রেইঞ্জের Almost Prime Number গুলু বের করে ফেলতে পারি কিংবা বলতে পারি ওই রেইঞ্জে কতগুলু Almost Prime Number আছে । 
কিন্তু কোডিংয়ে বিষয়টা একটু অন্য ভাবে চিন্তা করতে হবে । কেননা TLE এড়ানোর জন্য আমরা সবসময় ট্রাই করি পাওয়ার নিয়ে কাজ কম করার, তবে তা যদি কেবল ছোট রেইঞ্জের হয় তাহলে ঠিক আছে ... কিন্তু লিমিট টা যদি দশের পরে ১১ বা ১২ টা শূন্যের বোঝা মাথায় চেপে দেওয়া হয় তাহলে অগত্যা এই পাওয়ার নিয়ে আমাদের আর কিছুই করার নেই । 
তাই আমরা উপরের কোডটিতে প্রতিটি প্রাইম নাম্বারের জন্য তাঁর কাঙ্ক্ষিত লিমিট পর্যন্ত কেবল একটা আরেকটার সাথে গুণ করে গেছি এবং স্টোর করেছি ।। 
কোডটা অনেক সোজা, তাই আশা করি কার প্রবলেম হবে না ।।
তো, এভাবেই আমরা কোন প্রবলেম ছাড়াই খুব সহজেই Almost Prime Number গুলু বের করে ফেলতে পারি ।। তবে আবার বলছি ... Almost Prime Number গুলু কিন্তু একটাও Prime Number না । বরং Prime Number গুলু থেকেই এদের উৎপত্তি ।। 
..................... এবার https://uva.onlinejudge.org/external/105/10539.pdf এই প্রবলেম টি আশা করি করে ফেলতে পারবেন ।। 
তারপরও যদি না পারেন এই লিঙ্কে http://psshidhu.blogspot.com/2015/10/uva-10539-almost-prime-numbers.html গিয়ে হেল্প নিতে পারেন ।। তবে কখনও কোড কপি-পেস্ট করবেন না । আগে নিজে ট্রাই করে পরে হেল্প নিবেন ।।
সব শেষে অনেক শুভ কামনা রইল । । । । 
 .................................................................. Happy Coding .....................

নাম্বার থিওরি

আমি নাম্বার থিওরি শুরু করি আমাদের অমিত স্যার এর ACM ক্লাসে "Sieve of Eratosthenis" এর মাধ্যমে । পরে এই প্রবলেম নিয়ে বেশ কিছু প্রবলেম সল্ভিং দিয়ে পুরাপুরিভাবে আমি নাম্বার থিওরি যাত্রা শুরু করি ।
ইতিমধ্যে নাম্বার থিওরি এবং প্রাইম রিলেইটেড বেশ কিছু প্রবলেম নিয়ে ঘাটাঘাটি করা হয়েছে ।
তাঁর মধ্যে নাম্বার থিওরি বা প্রাইম (যাই বলুন) কিছু প্রবলেম শেয়ার করছি ...

[এর বাইরে আমি যার সাহায্য নিয়েছিলাম তাঁর লিঙ্কঃ http://lightoj.com/article_show.php?article=1001 ]

[ সব Uva প্রবলেম ]

  

1. Uva 324 - https://uva.onlinejudge.org/external/3/324.pdf
 === নরমাল ফেক্টোরিয়াল প্রবলেম । কিন্তু ১০০! এর কথা মাথায় রাখতে হবে ।।
== সমাধানঃ http://psshidhu.blogspot.com/2015/10/uva-324-factorial-frequencies.html

2. Uva 10948 - https://uva.onlinejudge.org/external/109/10948.pdf
===== একটি আদর্শ নাম্বার থিওরি প্রবলেম বলা যায় । বলে রাখি, Uva তে ম্যাক্সিমাম নাম্বার-থিওরি প্রবলেম TLE পাবার মত অবস্থায় থাকে । তাই সল্ভ করার আগে অবশ্যই সাতপাঁচ ভেবে সল্ভ করা উচিত ।

3. Uva 11417 - https://uva.onlinejudge.org/external/114/11417.pdf
==== খুব নরমাল GCD প্রবলেম ।। সবার করা উচিত ।

4. Uva 10924 - https://uva.onlinejudge.org/external/109/10924.pdf
==== এটাও খুব সোজা । কিন্তু তারপরো দেখে শুনে !!! সাবধানের মার নেই ।

5.  Uva 10533 - https://uva.onlinejudge.org/external/105/10533.pdf
======== হুম ! চরম পেইনময় এক প্রবলেম । আবার পয়েন্ট ২ এর বল্ড করা কথাটা স্মরণ করিয়ে দেই ...

6. Uva 10323 - https://uva.onlinejudge.org/external/103/10323.pdf
==== নরমাল ফেক্টোরিয়াল প্রবলেম। কিন্তু অনেক মডিফিকেশন আছে । তাই কোড করার আগে সাবধানে এবং ভাল করে চিন্তা ভাবনা করে করুন ।

7. Uva 10338 - https://uva.onlinejudge.org/external/103/10338.pdf
====== অনেক মজার একটা প্রবলেম । নিজের কমন সেন্স আর ইন্টারমিডিয়েটের factorial এর অংকগুলুর আইডিয়া কাজে লাগান। [ বলে রাখি এই প্রবলেম টি next_permutation STL ব্যবহার করেও করা যায় । কিন্তু শতভাগ TLE পাবার আশা করেই তবে ট্রাই দিয়েন । কেননা আমি যতদূর জানি next_permutation STL এর টাইম কমপ্লেক্সিটি O(n) । এখন আপনার ১২! এর জন্য কমপ্লেক্সিটি আসবে O(n!) ... আপনার পিসি হয়ত এর ঠিকঠাক আউটপুট দিয়ে দিবে , কিন্তু জাজের পিসি দিবে না । তাই আপনাকে এমন একটা Algorithm তৈরি করতে হবে যা কি না efficient . ]

8. Uva 10394 - https://uva.onlinejudge.org/external/103/10394.pdf
===== এই প্রবলেম টা করতে গিয়ে অনেক মজা পেয়েছি । অনেক ভাল একটা প্রবলেম । তবে যদি অ্যারে দিয়ে করতে চান তাহলে সাইজের প্রতি খেয়াল রাখবেন ।

9. Uva https://uva.onlinejudge.org/external/113/11388.pdf
====== এটা সহজ । যখন দেখবেন তখনেই করে ফেলা উচিত ...

10. Uva https://uva.onlinejudge.org/external/107/10789.pdf
==== একটু চিন্তা মূলক প্রবলেম । প্রাইম আর ক্যারেকটারের মিশেল । তবে সহজ ।

11. Uva https://uva.onlinejudge.org/external/102/10235.pdf
===== এটাও খুব একটা কঠিন না । সিভ জেনারেইট করতে পারলে এটা পারা কোন ব্যাপার না ।

12. Uva https://uva.onlinejudge.org/external/4/406.pdf
=== এক লজিকের প্রবলেম । আর সিভ তো আছেই । তাই প্রবলেম টা খুব কঠিন না ।

13. Uva https://uva.onlinejudge.org/external/4/412.pdf
====== এটা পাই এর প্রবলেম । বিভিন্নভাবে পাই এর ভ্যালু জানারেইট করতে হবে এই যা ...

14. Uva https://uva.onlinejudge.org/external/104/10490.pdf
==== এটা বেশ ভাল নাম্বার থিওরি প্রবলেম । পারফেক্ট নাম্বার খুজে বের করতে হবে । যার সূত্র হচ্ছে 2^p-1 * ( (2^p ) - 1) where p is a prime number.. এখন করার দায়িত্ব আপনার ।

15. Uva https://uva.onlinejudge.org/external/6/623.pdf
==== নরমাল factorial প্রবলেম । তবে ৫০০! বুঝতেই পারছেন । সি++ এর ক্ষেত্রে স্ট্রিং এবং জাভার ক্ষেত্রে বিগইন্টিজার ব্যবহার করতে হবে ।

16. Uva https://uva.onlinejudge.org/external/9/974.pdf
 === আরেকটি খুব ভাল নাম্বার থিওরি প্রবলেম । কাপ্রেকার নাম্বার গুলু খুজে বের করতে হবে । যেমন ৫৫^২ = ৩০২৫ । আবার (৩০ + ২৫) = ৫৫ ।। কিন্তু ১০ বা ১০০০ বা ১০০০০ এর ক্ষেত্রে হবে না । এইভাবে ৪০০০০ নাম্বারের ক্ষেত্রে কাপ্রেকার নাম্বার খুজে বের করতে হবে ।

17. Uva https://uva.onlinejudge.org/external/4/495.pdf
==== ফিবোনাচ্চি নাম্বার খুজে বের করতে হবে । সাইজের কথা উল্লেখ নেই । তাই WA এড়াতে বিগইন্টিজার বা পারলে স্ট্রিং দিয়ে করুন।

18. Uva  900 - https://uva.onlinejudge.org/external/9/900.pdf
==== ফিবোনাচ্চি প্রবলেম । নিজেই করে ফেলুন ।

 [ আসলে, এই ছিল আমার  কিছু কালেকশন আমার আয়ত্তে । এটাই শেষ না তবে নিঃসন্দেহে এটা Uva মোট নাম্বার থিওরি প্রবলেমের খুব বেশি হলে ১% বা ২% । তাই নাম্বার থিওরি নিয়ে আরও বেশি জানতে হলে আরও বেশি বেশি প্রবলেম সল্ভ করার কোন বিকল্প নেই । ]