0 like 0 dislike
3,608 views
| 3,608 views

1 like 0 dislike

C++ code :

```// A modular inverse based solution to
// compute nCr % p
#include <bits/stdc++.h>
using namespace std;

/* Iterative Function to calculate (x^y)%p
in O(log y) */
unsigned long long power(unsigned long long x,
int y, int p)
{
unsigned long long res = 1; // Initialize result

x = x % p; // Update x if it is more than or
// equal to p

while (y > 0)
{

// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;

// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
int p)
{
return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
int r, int p)
{
// If n<r, then nCr should return 0
if (n < r)
return 0;
// Base case
if (r == 0)
return 1;

// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
unsigned long long fac[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % p;

return (fac[n] * modInverse(fac[r], p) % p
* modInverse(fac[n - r], p) % p)
% p;
}

// Driver program
int main()
{
// p must be a prime greater than n.
int n, r, p ;
cin>>n>>r>>p ;

cout << "Value of nCr % p is "
<< nCrModPFermat(n, r, p);
return 0;
}
```
by Expert (107,750 points)
selected
0 like 0 dislike

C++ code :

```// C++ program to count number of factors
// of an array of integers
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
const int MAX = 1000001;
ll dp[1000000+5];
// array to store prime factors
int factor[MAX] = { 0 };
vector <ll> G[MAX+5] ;
// function to generate all prime factors
// of numbers from 1 to 10^6
void generatePrimeFactors()
{
factor[1] = 1;

// Initializes all the positions with their value.
for (int i = 2; i < MAX; i++)
factor[i] = i;

// Initializes all multiples of 2 with 2
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;

// A modified version of Sieve of Eratosthenes to
// store the smallest prime factor that divides
// every number.
for (int i = 3; i * i < MAX; i++) {
// check if it has no prime factor.
if (factor[i] == i) {
// Initializes of j starting from i*i
for (int j = i * i; j < MAX; j += i) {
// if it has no prime factor before, then
// stores the smallest prime divisor
if (factor[j] == j)
factor[j] = i;
}
}
}
}

// function to calculate number of factors
void calculateNoOfFactors(int n)
{
int index = n ;
if (n == 1){
//        return 1;
}
int ans = 1;

// stores the smallest prime number
// that divides n
int dup = factor[n];
//cout<<dup;
//cout<<"\n";
G[index].push_back(dup);
// stores the count of number of times
// a prime number divides n.
int c = 1;

// reduces to the next number after prime
// factorization of n
int j = n / factor[n];

// false when prime factorization is done
while (j != 1) {
// if the same prime number is dividing n,
// then we increase the count
if (factor[j] == dup)
c += 1;

/* if its a new prime factor that is factorizing n,
then we again set c=1 and change dup to the new
prime factor, and apply the formula explained
above. */
else {
dup = factor[j];
//cout<<dup;
//cout<<"\n";
G[index].push_back(dup);
ans = ans * (c + 1);
c = 1;
}

// prime factorizes a number
j = j / factor[j];
}

// for the last prime factor
ans = ans * (c + 1);

//return ans;
}

// Driver program to test above function
int main()
{

generatePrimeFactors();
dp[1] = 1 ;
dp[2] = 2 ;

//     int a[] = {105};

//     int q = sizeof(a) / sizeof(a[0]);

//     for (int i = 0; i < q; i++){
//         cout << calculateNoOfFactors(a[i]) << " ";}

ll i = 2 ;
while(i<=250000+55){

calculateNoOfFactors(i);
sort(G[i].begin(),G[i].end());
i++;
}

i = 3 ;
while(i<=250000+55){
ll oo = G[i].size();

ll vv = G[i][oo-1];
if(vv!=1 && vv!=i){
dp[i] = 1 + min(dp[i-1],dp[vv]);
}
else
{
dp[i] = dp[i-1] + 1 ;
}

i++;
}
ll n;
cin>>n ;
cout<<dp[n] ;
return 0;
}
```
by Expert (107,750 points)
edited