ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1055. Combinations

why I get crash(access violation) at test 6?
Posted by rongyan 13 Sep 2006 18:15
why I get crash(access violation) at test 6?
who have the test?
S.O.S!!
Re: why I get crash(access violation) at test 6?
Posted by Blum 25 Nov 2007 04:40
50000 2
Re: why I get crash(access violation) at test 6?
Posted by Vasil Todorov 20 Feb 2009 01:41
This is not test 6! The answer of 50000 2 is 3 and my program shows it but i have WA on test 6!!!
Re: why I get crash(access violation) at test 6?
Posted by Varun Sharma 18 Apr 2009 15:32
Lol, the question was asked in 2006, first answer came in 2007 and the second one in 2009 ! vava viva !
Re: why I get crash(access violation) at test 6?
Posted by nguyenductam 5 Apr 2010 10:27
Delete

Edited by author 05.04.2010 10:36

Edited by author 05.04.2010 10:36
use legendre formula to count how many times prime contains in n!
Posted by Baurzhan 5 Apr 2010 12:44
#include<iostream>
using namespace std;

bool prime[50001];
int primes[6000],len=0;
int n,m;
int primesUp[6000];
int primesDown[6000];
long long ans = 0;

long long legendre(long long num,long long p){
    long long c = 0;
    long long tmp = p;
    while( (num/p) !=0){
        c+=num/p;
        p*=tmp;
    }
    return c;

}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

cin>>n>>m;
memset(prime,true,sizeof(prime));
for(int i=2;i<=223;i++){
    if(prime[i]){
        for(int j=i+i;j<=50000;j+=i)
            prime[j] = false;
        }
    }
for(int i=2;i<=n;i++){
    if(prime[i]){
        primes[len] = i;
        len++;
    }
}
for(int i=0;i<len;i++){
    primesUp[i] += legendre(n,primes[i]);
    primesDown[i] += legendre(m,primes[i]);
    primesDown[i] += legendre(n-m,primes[i]);
}
for(int i=0;i<len;i++){
    if(primesUp[i] > primesDown[i])
    ans++;
}
cout<<ans<<endl;
return 0;
}