সমাবেশ (Combination) Calculation nCr

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

long long ara[52][52];
long long nCr(int n, int r)
{
    if(n == r) return 1;
    if(r == 1) return n;
    if(ara[n][r]!=0) return ara[n][r];
    return ara[n][r] = nCr(n-1, r) + nCr(n-1, r-1);
}
int main()
{
    int n = 50, r = 25;
    long long ans = nCr(n, r);
    cout << ans << endl;
    return 0;
}

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int zero(int x)
{
    int ans = 0;
    for(int i=5; x/i>0;i*=5)
        ans += x/i;
    return ans;
}
int main()
{
    int n;
    cin >> n ;
    cout << zero(n) << endl;
    return 0;
}

int main()
{
    int ans = bigMod(4, 100001, 1234);
    cout << ans << endl;
    return 0;
}

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int bigMod(int a, int n, int m)
{
    //here, a, n and m refer to (a^n)%m

    if(n==0) return 1 % m ;
    int x = bigMod(a, n/2, m);
    x = (x*x) % m;
    if(n%2) x = (x*a)%m;
    return x%m;
}
int main()
{
    int ans = bigMod(4, 100001, 1234);
    cout << ans << endl;
    return 0;
}

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

unsigned long long int phi[5000005];
int mark[5000005];

void seivePhi()
{
    for(int i=2; i<=5000002; i++) phi[i] = i;
    for(int i=2; i<=5000002; i++)
        if(!mark[i])
            for(int j=i; j<=5000002; j+=i)
            {
                mark[j] = 1;
                phi[j] = phi[j]/i * (i-1);
            }
    for(long long int i=3; i<5000002; i++)
    {
        phi[i] *= phi[i];
        phi[i] += phi[i-1];
    }

}
int main()
{
    seivePhi();
    int tst;
    unsigned long long int ans, a, b;
    scanf("%d", &tst);
    for(int i=1; i<=tst; i++)
    {
        scanf("%llu%llu", &a, &b);
        ans = phi[b] - phi[a-1];
        printf("Case %d: %llu\n", i, ans);
    }
    return 0;
}

অয়লার এর টোশেন্ট ফাংশন (Euler's Totient unction) {n পর্যন্ত সকল সংখ্যার জন্য}

n এর থেকে ছাট বা সমান এমন কতগুলি সংখ্যা আছে যা n এর সাথে coprime। coprime অর্থ হল তাদের ১ ছাড়া কোন সাধারণ গুণনীয়ক নেই।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int phi[10005], mark[10005];

void seivePhi(int n)
{
    for(int i=2; i<=n; i++) phi[i] = i;
    for(int i=2; i<=n; i++)
        if(!mark[i])
            for(int j=i; j<=n; j+=i)
            {
                mark[j] = 1;
                phi[j] = phi[j]/i * (i-1);
            }
}
int main()
{
    int n;
    scanf("%d", &n);
    seivePhi(n);
    for(int i=1; i<=n; i++)
        printf("Number of Coprime for %4d is %4d\n", i, phi[i]);
    return 0;
}

অয়লার এর টোশেন্ট ফাংশন (Euler's Totient Function) {শুধুমাত্র একটি সংখ্যা n এর জন্য}

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int Phi(int n)
{
    int ans = n;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            ans -= ans/i;
        }
    }
    if(n>1) ans -= ans/n;
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    int ans = Phi(n);
    printf("Number of Coprime for %d is %d\n", n, ans);
    return 0;
}

ল.সা.গু (LCM) (দুই এবং দুইয়ের অধিক সংখ্যার জন্য)

দুইটি সংখ্যার জন্য ল.সা.গুঃ

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b)
{
    if(b==0) return a;
    return GCD(b, a%b);
}
int LCM(int a, int b)
{
    int gcd = GCD(a, b);
    return (a/gcd)*b;
}
int main()
{
    int a, b, ans;
    cin >> a >> b;
    ans = LCM(a,b);
    cout << ans << endl;
    return 0;
}

দুইটির বেশী সংখ্যার জন্য ল.সা.গুঃ

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b)
{
    if(b==0) return a;
    return GCD(b, a%b);
}
int LCM(int a, int b)
{
    int gcd = GCD(a, b);
    return (a/gcd)*b;
}
int main()
{
    int ans, n;
    cin >> n;
    int ara[n];
    for(int i=0; i<n; i++)
        cin >> ara[i];
    ans = ara[0];
    for(int i=1; i<n; i++)
        ans = LCM(ans, ara[i]);
    cout << ans << endl;
    return 0;
}

গ.সা.গু (GCD) (দুই এবং দুইয়ের অধিক সংখ্যার জন্য)

দুইটি সংখ্যার জন্য গ.সা.গুঃ

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b)
{
    if(b==0) return a;
    return GCD(b, a%b);
}
int main()
{
    int a, b, ans;
    cin >> a >> b;
    ans = GCD(a,b);
    cout << ans << endl;
    return 0;
}

দুইটির বেশী সংখ্যার জন্য গ.সা.গুঃ

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b)
{
    if(b==0) return a;
    return GCD(b, a%b);
}
int main()
{
    int ans, n;
    cin >> n;
    int ara[n];
    for(int i=0; i<n; i++)
        cin >> ara[i];
    ans = ara[0];
    for(int i=1; i<n; i++)
        ans = GCD(ans, ara[i]);
    cout << ans << endl;
    return 0;
}

Sum of Divisor (SOD) using 2 Method

একটি সংখ্যা n দেওয়া আছে। এর বিভাজকের যোগফল বের করতে হবে।

Method 1: রোট পর্যন্ত লোপ চালিয়ে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;


int SOD(int n)
{
    int limit = sqrt(n+1);
    int res = 0;
    for(int i=1; i<=limit; i++)
        if(!(n%i))
        {
            res += i;
            res += (n/i);
        }
    if(limit*limit==n) res -= limit;
    return res;
}
int main()
{
    int ans, n;
    scanf("%d", &n);
    ans = SOD(n);
    printf("%d\n", ans);
    return 0;
}

Method 2: প্রাইম ফ্যাক্টরাইজড করে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int prime[4009], x=1;

void seivePrime()
{
    char prime_b[10000];
    memset(prime_b, 0, sizeof(prime_b));
    int till = 10000;
    for(int i=4; i<=till; i+=2)
        prime_b[i] = 1;
    int limit = sqrt(till)+1;
    for(int i=3; i<=limit; i+=2)
        if(!prime_b[i])
            for(int j=i*i; j<=till; j+=(i*2))
                prime_b[j] = 1;
    prime[0] = 2;
    for(int i=3; i<=till; i+=2)
        if(!prime_b[i])
            prime[x++] = i;
}
int SOD(int n)
{
    int till = sqrt(n+1), res=1;
    for(int i=0; prime[i]<=till; i++)
    {
        if(n%prime[i]==0)
        {
            int tmpSum = 1, p = 1;
            while(n%prime[i]==0)
            {
                n/=prime[i];
                p *= prime[i];
                tmpSum += p;
            }
        till = sqrt(n);
        res *= tmpSum;
        }
    }
    if(n>1) res *= (n+1);
    return res;
}
int main()
{
    seivePrime();
    int ans, n;
    scanf("%d", &n);
    ans = SOD(n);
    printf("%d\n", ans);
    return 0;
}

Number of Divisor (NOD) using 2 Method

একটি সংখ্যা n দেওয়া আছে। এর কয়টি বিভাজক আছে বের করতে হবে।

Method 1: রোট পর্যন্ত লোপ চালিয়ে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int NOD(int n)
{
    int limit = sqrt(n+1);
    int res = 0;
    for(int i=1; i<=limit; i++)
        if(!(n%i))
            res += 2;
    if(limit*limit==n) res--;
    return res;
}
int main()
{
    int ans, n;
    scanf("%d", &n);
    ans = NOD(n);
    printf("%d\n", ans);
    return 0;
}

Method 2: প্রাইম ফ্যাক্টরাইজড করে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int prime[4009], x=1;

void seivePrime()
{
    char prime_b[10000];
    memset(prime_b, 0, sizeof(prime_b));
    int till = 10000;
    for(int i=4; i<=till; i+=2)
        prime_b[i] = 1;
    int limit = sqrt(till)+1;
    for(int i=3; i<=limit; i+=2)
        if(!prime_b[i])
            for(int j=i*i; j<=till; j+=(i*2))
                prime_b[j] = 1;
    prime[0] = 2;
    for(int i=3; i<=till; i+=2)
        if(!prime_b[i])
            prime[x++] = i;
}

int NOD(int n)
{
    int till = sqrt(n+1);
    int p=0, res = 1;
    for(int i=0; prime[i]<=till; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
                p++;
            }
        }
        till = sqrt(n);
        res *= (p+1);
        p = 0;
    }
    if(n>1) res *= 2;
    return res;
}
int main()
{
    seivePrime();
    int ans, n;
    scanf("%d", &n);
    ans = NOD(n);
    printf("%d\n", ans);
    return 0;
}

Solution of Light OJ 1035 : Intelligent Factorial Factorization (প্রাইম ফ্যাক্টোরাইজেশন)

প্রাইম ফ্যাক্টোরাইজেশন করতে হবে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

vector<int> ara[101];


void primeFactor()
{
    for(int j=2; j<=100; j++)
    {
        int tmp = j;
        while(tmp%2==0)
        {
            tmp/=2;
            ara[j].push_back(2);
        }
        int limit = sqrt(tmp+1);
        for(int i=3; i<=limit && tmp>1; i+=2)
            while(tmp%i==0)
            {
                tmp/=i;
                ara[j].push_back(i);
            }
        if(tmp > 2) ara[j].push_back(tmp);
    }
}
int main()
{
    primeFactor();
    int tst, n;
    scanf("%d", &tst);
    for(int i=1; i<=tst; i++)
    {
        scanf("%d", &n);
        int ans[103];
        memset(ans, 0, sizeof(ans));
        for(int k=2; k<=n; k++)
            for(int l=0; l<ara[k].size(); l++)
                ans[ara[k][l]]++;
        for(int j=2, first=1; j<=100; j++)
            if(ans[j]>0)
            {
                if(first==1)
                {
                    printf("Case %d: %d = %d (%d)", i, n, j, ans[j]);
                    first = 0;
                }
                else printf(" * %d (%d)", j, ans[j]);
            }
        printf("\n");
    }
    return 0;
}

Solution of Light OJ 1197 : Help Hanzo (সেগমেনটেড সীভ)

মেইনলি সেগমেন্টেড সীভ ব্যবহার করে সল্ভ করতে হবে।

/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int prime[7809], x=1;

void seivePrime()
{
    char prime_b[46350];
    memset(prime_b, 0, sizeof(prime_b));
    prime_b[1]=1;
    int till = 46349;
    for(int i=4; i<=till; i+=2)
        prime_b[i] = 1;
    int limit = sqrt(till)+1;
    for(int i=3; i<=limit; i+=2)
    {
        if(!prime_b[i])
        {
            for(int j=i*i; j<=till; j+=(i*2))
                prime_b[j] = 1;
        }
    }
    prime[0] = 2;
    for(int i=3; i<=till; i+=2)
        if(!prime_b[i])
            prime[x++] = i;
}
long long segment_prime(long long A, long long B)
{
    if(A==1) A++;
    char segment[B-A+1];
    memset(segment, 0, sizeof(segment));
    long long till = sqrt(B)+1, cnt=0;
    for(long long i=0; i<x && prime[i]<=till; i++)
    {
        long long start = prime[i]*prime[i];
        if(start<A) start = ((A+prime[i]-1)/prime[i])*prime[i];
        for(; start<=B; start += prime[i])
            segment[start-A] = 1;
    }
    if(A<=2 && B>=2) cnt++;
    long long j=A+1;
    if(A%2) j=A;
    for(; j<=B; j+=2)
        if(!segment[j-A])
            cnt++;
    return cnt;
}
int main()
{
    seivePrime();
    int tst;
    scanf("%d", &tst);
    for(int k=1; k<=tst; k++)
    {
        long long a, b, cnt = 0;
        scanf("%lld %lld", &a, &b);
        cnt = segment_prime(a, b);
        printf("Case %d: %lld\n", k, cnt);
    }
    return 0;
}

কোড ওয়ার্কশপ

মো.মাহবুবুল হাসান (শান্ত) ভাইয়ের "প্রোগ্রামিং কন্টেস্ট" বইয়ের কোড ভার্সন

Blog Archive