Subarrays with distinct elements

#1

I found the problem statement of the question to be unclear. Please explain it

#2

Add the problem link.

#3

Please explain the solution for this problem under BITMASKING challenges…
problem name----NOT SO EASY MATH

#4

This question belongs to inclusion-exclusion. Think in terms of inclusion exclusion. Note that numbers divisible by i that are less than equal to N, are: floor(N/i).
Think and let me know in case of any doubts.

#5

https://ide.codingblocks.com/s/47173

here is my submission for your reference.

#6

problem=(NOT SO EASY MATH)
I am not getting it right…Have a look, please

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll number=0;
ll ans3=0,ans6=0,ans8=0;

ll solve4(){
ll cnt=0;
ll arr1[3]={2,3,5},arr2[3]={7,11,13},arr4[2]={17,19};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<2;k++){
cnt+=number/(arr1[i]*arr2[j]*arr4[k]);
}
}
}
return cnt;
}

ll solve3(ll arr1,ll arr2 ,int n,int m){
ll cnt=0;
for(int i=0;i<n;i++){
ll f=(arr1+i);
for(int j=0;j<m;j++){
ll s=(arr2+j);
cnt+=number/(fs);
}
}
return cnt;
}
ll final_Ans(ll a,ll b,ll c){
ll arr3[3]={2,3,5},arr6[3]={7,11,13},arr8[2]={17,19};
ll ans36=solve3(arr3,arr6,3,3);//evaluating intersection to get ans36
ll ans68=solve3(arr6,arr8,3,2);//evaluating intersection to get ans68
ll ans83=solve3(arr8,arr3,2,3);//evaluating intersection to get ans83
ll ans368=solve4();//evaluating intersection to get ans368
ll ans=a+b+c-ans36-ans68-ans83+ans368;//inclusion-exclusion formula
return ans;
}
ll solve2(ll a,ll b){
ll A=number/a,B=number/b,AB=number/(ab);
ll ans=A+B-AB;
return ans;
}

ll solve1(ll a,ll b,ll c){
ll A=number/a,B=number/b,C=number/c;
ll AB=number/(ab), BC=number/(bc),CA=number/(ca),ABC=number/(ab*c);
//cout<<A<<" “<<B<<” “<<C<<” “<<AB<<” “<<BC<<” “<<CA<<” "<<ABC<<endl;
ll ans=A+B+C-AB-BC-CA+ABC;
return ans;
}

int main() {
ll t=0;
cin>>t;
while(t–){
cin>>number;
ans3=solve1(2,3,5);//calculating N(AUBUC) no of numbers divisible by 2 or 3 or 5
ans6=solve1(7,11,13);//calculating …7 or 11 or 13
ans8=solve2(17,19);//calculating N(AUB) for 17, 19
ll finalAns=final_Ans(ans3,ans6,ans8);//applying union on results obtained from above function calls
//cout<<ans3<<" “<<ans6<<” "<<ans8<<endl;
cout<<finalAns<<endl;
}
return 0;
}

#7

Code is too complicated. Please see my code once.

#8

Problem-- A Factorial Problem
After 2 hrs of struggle i decided for doubt discussion.

I am not able to get logic for querying the answer when k > 1000000 and when k is not a prime number.
what i am doing is that first, i am getting n! in the form of p1^x1 * p2^x2*…pk^xk
where pi is a prime number and it is raised to some power xi
and then taking the power of k(which is a prime number in my case) as the answer.
i know i am no where near to correct approach.

So please tell me how to deal with large and non-prime values of ‘k’.

Please reply as soon as possible.

#9

This problem can be solved in Log N to the base K complexity.
Lets say K is 2
And say N is 1000 in our case
1000!=1000*…86421…
Like this.
Number with power 2^1 atleasr = floor(1000/2)
Number with power 2^2 atleast = floor(1000/4)
Numbers with power 2^3 atleast = floor(1000/8)
And so on till rhs != 0.
Add all rhs: 500+250+125+62+31+15+7+3+1 = 994 = answer.
Try thinking this way and try this for small samples on paper.

#10

I am not able to think the logic for k>n…
My code–

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n=0,t=0,k=0;

void solve(){
ll cnt=0;
ll quotient=1,i=1;;
if(k>=n){
ll j=2;
while(j<=n){
if(k%j==0 && (k/j)<=n){
printf(“1\n”);
return;
}
j++;
}
printf(“0\n”);
return;
}
while(quotient!=0){
quotient=n/pow(k,i++);
cnt+=quotient;
}
printf("%lld\n",cnt);
}

int main(){
scanf("%lld",&t);
while(t–){
scanf("%lld%lld",&n,&k);
solve();

}
return 0;
}