Please help me with lets this question i am clueless

tanmay17 · January 27, 2020, 11:49am

Please help me with this ques i was trying it for all nos but as the question says the fr5action cant be reduced i have become clueless please explain the solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
map<int,int>mp;
int arr[n+1]={0};
int sum=1;
for(int i=2;i<=n;i++){
// cout<<"\n";
int num=i;
for(int j=2;jj<=i;){
while(num%j==0){
mp[j]++;
// cout<<mp[j]<<endl;
sum/=mp[j];
sum=(mp[j]+1);
// cout<<j<<" "<<sum<<endl;
num/=j;
}
if(j==2)j++;
else j+=2;
}
if(num>=2){
mp[num]++;
sum/=mp[num];
sum*=(mp[num]+1);
// cout<<mp[num]<<endl;
num/=num;
}
// for(auto c:mp){
// sum*=(c.second+1);
// }
arr[i]=(sum)/2+arr[i-1];
}
cout<<arr[n]<<endl;
return 0;
}

tanmay17 · January 29, 2020, 11:31am

help me with this please

tanmay17 · January 29, 2020, 11:32am

Why isn’t anyone replying to this

Robin_rst · January 30, 2020, 10:48pm

Refer this -:

github.com

robinrst/HackerBlocks/blob/master/MagicFraction.cpp

#include "bits/stdc++.h"
 
using namespace std;
 
#define  f first
#define  lgn 25
#define  endl '\n'
#define  sc second
#define  N (int)2e5+5
#define  sz(x) x.size()
#define  int long long int
#define  ld long double
#define  vi vector<int>
#define  vs vector<string>
#define  vc vector<char>
#define  mii map<int,int>
#define  pii pair<int,int>
#define  vpii vector<pii>
#define  test(x) while(x--)
#define  pb push_back

This file has been truncated. show original

Our objective is to factor n! into p and q such that hcf(p,q)=1 and p<q. so we calculate number of distinct primes in n!
let prime factorisation of n!= (p1)^x1 * (p2)^x2 …(pk)^xk
now for each i, (pi)^xi can either go in p or q. Hence 2^k ways. but as we want p<q. therefore only 2^(k-1) ways. That’s why in code, counting primes is started from 3 because ultimately we would have to subtract 1 from k.

Robin_rst · February 6, 2020, 4:12pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.