👨‍🍳Basic Math - Codechef

Codechef - Basic Math

Q1:

The chef wants to become fit for which he decides to walk to the office and return home by walking. It is known that Chef's office is X km away from his home.

If his office is open 5 days a week, find the number of kilometers the Chef travels through office trips in a week.

#include <iostream>
using namespace std;

int main() {
	int X;
	int tt;
	cin >> tt;
	while(tt--) {
	    cin>>X;
	    cout << (X*2)*5 << endl;
	}
	return 0;
}

Notes

Q1: Count Prime

Solve by using Sieve of Eratosthenes

int countPrimes(int n) {
    int cnt = 0;
    vector<bool> Prime(n+1, true);
    Prime[0] = Prime[1] = false;
    
    for(int i = 2; i < n; i++){
        if(Prime[i]){
            cnt++;
            for(int j = 2*i; j < n; j+=i){
                Prime[j] = false; 
            }
        }
    }
    return cnt;
}
      (n/2 + n/3 + n/5 + n/7...)
       n * (1/2 + 1/3 + 1/5 + 1/7...) //Harmonic Progression of Prime Number
T.C = O(n* Log(logn))

Segmented Sieve

Q2: Must read -> Euclid GCD Algorithm

GCD Formula: Find gcd until one of the parameters becomes zero

gcd(a - b, b)

gcd(a % b, b)

LCM & GCD Relation: LCM(a, b) * GCD(a, b) = a * b

Greatest Common Factor & Highest Common Factor

int GCD(int a, int b){
    if(a==0)
        return b;
    if(b==0)
        return a;
    while(a != b){
        if(a>b)
            a -= b;
        else{
            b -= a;
        }
    }
    return a;
    
    // recursively solved

    //Method - I
    if(a>b)
        return GCD(a-b, b);
    else
        return GCD(b-a, a);
    
    //Method - II --> for less number of iterations GCD(a,b) = GCD(a%b,b)
    if(a>b)
        return GCD(a%b, b);
    else
        return GCD(b%a, a);
}
int main(){
    int ans = GCD(25, 72);
    cout << ans;
}

Topic: Modular Arithmetic

( a%m + b%m) % m = (a + b) % m

(a%m − b%m) % m = (a − b) % m

(a%m * b%m) % m = (a * b) % m

Q3: Modular Exponentiation --> Notes Page # 05

Using Fast Exponentiation Algorithm T.C: O(logn)

int modularExponentiation(int n, int pow, int m) {
	int ans = 1;
	while(pow > 0){
		if(!(pow%2 == 0)){
			ans = (1LL * ans * n)%m;
		}
		n = (1LL * n * n)%m;
		pow /= 2;
	}
	return ans;
}