২৫ জানুয়ারি ২০১৬

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 ...


এর দ্বারা পোস্ট করা এই সময়ে কোন মন্তব্য নেই:

৩০ ডিসেম্বর ২০১৫

Big Mod

R = B^P mod M

 LL m;

LL big_mod(LL n, LL p)
{
    if(p==0) return 1;

    if(!(p&1))
    {
        LL r = big_mod(n,p/2) % m;

        return ( (r%m) * (r%m) ) % m;
    }

    else
    {
        return ( ( n%m) * (big_mod(n,p-1) %m)) % m;
    }
}

int main()
{
    LL b,p;

    while(~sf("%lld %lld %lld",&b,&p,&m))
    {
        pf("%lld\n",big_mod(b,p));
    }

    return 0;
}

পাওয়ার বা P যদি জোড় হয় তবে LL r = big_mod(n,p/2) % m; এই লাইন ইউস করা হইসে । এবং পরে একে অপরের সাথে গুন করা হইসে ।

তবে মনে রাখতে হবে মোড কিন্তু প্রত্যক অপারেশনের সাথে করতে হবে ।। 
পাওয়ার যদি বেজোড় হয় তাহলে n এর মোডের সাথে P-1 গুন করে দিতে হবে । কারন 2^25 = 2 * 2^24 ;

আর হ্যাঁ , অবশ্যই প্রত্যেকের সাথে m mod করতে হবে ।।



********* আমরা যে নাম্বার দিয়ে কোন নাম্বার কে ভাগ করি তাকে বলি ভাজক, যে নাম্বারকে ভাগ করা হচ্ছে তাকে বলে ভাজ্য , ভাগ করে আমরা যে রেজাল্ট পাই তাকে বলে ভাগফল, আর যা অবশিষ্ট থাকে তাকে বলে ভাগশেষ । আমরা মোড করে কেবল ভাগশেষ পাই ।।

**** তো মোড করলে একটা লাভ হয় যে , আমরা বিশাল বড় একটা রেজাল্টকে অনেক ছোট করে ফেলতে পারি ।। এবং মনে রাখতে হবে  "" কোন ভাগশেষ কখনও ভাজ্য থেকে বড় হতে পারে না । "" 

আরেকটু ভাল ভাবে বললে, ভাগশেষ < ভাজ্য , মানে কোনো সংখ্যাকে m দিয়ে mod করা হলে সংখ্যাটি m এর থেকে বড় হতে পারবেনা।









এর দ্বারা পোস্ট করা



এই সময়ে





 কোন মন্তব্য নেই:
  

















লেবেলসমূহ:
















          

        

          

        

২৭ ডিসেম্বর ২০১৫


          

        









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



নাম্বার থিওরির খুব গুরুত্তপূর্ণ একটা টপিক হচ্ছে এই 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 =  23 * 31 * 51

 φ(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... 















এর দ্বারা পোস্ট করা



এই সময়ে





 কোন মন্তব্য নেই:
  

















লেবেলসমূহ:
















        

      









এতে সদস্যতা:
পোস্টগুলি (Atom)