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;
}
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
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;
}
( a%m + b%m) % m = (a + b) % m
(a%m − b%m) % m = (a − b) % m
(a%m * b%m) % m = (a * b) % m
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;
}
