> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/basic-math-codechef.md).

# Basic Math - Codechef

## [Codechef - Basic Math](https://www.codechef.com/practice/basic-math-cpp)

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

```cpp
#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](https://drive.google.com/file/d/1loIOO_WWechujjzOcZz31ax2-FObjVvJ/view)

## `Q1:`  [Count Prime](https://leetcode.com/problems/count-primes/)

{% code title="Solve by using Sieve of Eratosthenes" overflow="wrap" %}

```cpp
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))
```

{% endcode %}

### Segmented Sieve

## `Q2:` <mark style="color:red;">Must read</mark> -> [Euclid GCD Algorithm](https://www.codingninjas.com/studio/library/gcd-euclidean-algorithm)

> #### <mark style="color:blue;">**GCD Formula:**</mark>   Find gcd until one of the parameters becomes zero
>
> #### &#x20;                              gcd(a - b,  b)
>
> #### &#x20;                              gcd(a % b,  b)
>
> #### <mark style="color:blue;">LCM & GCD Relation:</mark>      LCM(a, b)  \*  GCD(a,  b) = a \* b

<pre class="language-cpp" data-title="Greatest Common Factor &#x26; Highest Common Factor" data-overflow="wrap"><code class="lang-cpp">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;
    
<strong>    // recursively solved
</strong>
    //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 &#x3C;&#x3C; ans;
}
</code></pre>

## Topic: [Modular Arithmetic](https://codeforces.com/blog/entry/72527)

#### ( 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](https://www.codingninjas.com/studio/problems/modular-exponentiation_1082146) --> Notes Page # 05

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

{% code fullWidth="false" %}

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

{% endcode %}