সমাবেশ (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;
}

Read More

ফেক্টরিয়ালের পেছনের ০ (Trailing Zeros on Factorial)

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

Read More

বিগমড (Bigmod)

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

Read More

Solution of Light OJ 1007 : Mathematically Hard (অয়লার এর টোশেন্ট ফাংশন)

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

Read More

অয়লার এর টোশেন্ট ফাংশন (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;
}

Read More

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

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

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

Read More