HII..................
There is nice logic for this problem.......
LOGIC::
1.if u want to find out the number of occurences of any number in n!.
2.for this just divide the number by that number until number become zero
3.add the result each time to your answer...
ex: let u want to found out number of occurences of 5 in 100!
int ans=0;
n=100
while(n>0):
ans+=(n/5)
n/=5
print ans
LOGIC BEHIND THIS QUESTION::::
1.here u have to use the sieve for finding all primes upto max value of n
2.then use above logic
HERE IS MY AC C++ solution is>>>>>>>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | #include<bits/stdc++.h>
using namespace std;
#define max 10001
#define LL long long
LL prime[max];
void pre()
{
LL i,j;
prime[0]=1;
prime[1]=1;
for(i=2;i*i<max;i++)
{
for(j=i*i;j<max;j+=i)
prime[j]=1;
}
}
int main()
{
pre();
LL n,x,y,i,j,p;
scanf("%lld",&n);
//LL ans[n+1];
x=0; y=n;
while(y)
{
y>>=1;
x+=y;
}
printf("2^%lld ",x);
for(i=3;i<=n;i+=2)
{
if(prime[i]==0)
{
j=i;
p=n;
x=0;
while(p)
{
p/=j;
x+=p;
}
printf("* %lld^%lld ",i,x);
}
}
return 0;
}
|
No comments:
Post a Comment