Discussion @ 1055. Combinations @ Timus Online Judge

luckysundog tests [1] // Problem 1055. Combinations 16 Dec 2011 12:31

Ilya What answer if N<M ? [1] // Problem 1055. Combinations 2 Jun 2011 17:25

inatial_D the problem is not worth difficuity 349.. it's almost same as 1049. // Problem 1055. Combinations 7 Apr 2013 08:24

Abzal WA5 [2] // Problem 1055. Combinations 22 Aug 2011 15:46

nguyenductam Why WA in test 2. My code here. Please help me. [2] // Problem 1055. Combinations 5 Apr 2010 10:15

#include<stdio.h>
#include<conio.h>

long int i,j,n,m,aa,bb,cc,lap,k,l;
int a[50001],sont;
int dem[50001];
long int kq;

void InitPrime();
long int Max(long int x,long int y);
long int Min(long int x,long int y);
void InitDem();
void Test();

int main()
{
    scanf("%ld %ld",&n,&m);
    aa=Max(n,m);
    bb=Min(n,m);
    cc=aa-bb;

    InitDem();
    InitPrime();
//   Test();

    lap=Max(bb,cc);
    i=lap+1;
    // tinh so nguyen to o tren tu
    while(i<=aa)
    {
           k=0;
           l=i;
           while(l!=1)
           {
            k++;
            while((l%a[k])==0)
            {
             l=l/a[k];
             dem[a[k]]++;
            }
           }
           i++;
    }

    // tinh so nguyen to duoi mau
    lap=Min(bb,cc);
    i=2;
    // tinh so nguyen to o tren tu
    while(i<=lap)
    {
           k=0;
           l=i;
           while(l!=1)
           {
            k++;
            while((l%a[k])==0)
            {
             l=l/a[k];
             dem[a[k]]--;
            }
           }
           i++;
    }

    //dem ket qua
    kq=0;
    i=2;
    while(i<=aa)
    {
     if(dem[i]!=0) kq+=dem[i];
     i++;
    }
    printf("%ld",kq);

    getch();
    return 0;
}

void InitDem()
{
i=1;
while(i<=aa)
{
dem[i]=0;
i++;
}
}

long int Max(long int x,long int y)
{
if(x<=y) return y;
return x;
}

long int Min(long int x,long int y)
{
if(x<=y) return x;
return y;
}

void InitPrime()
{
     int flag;
     long int x;
     a[1]=2;
     a[2]=3;
     a[3]=5;
     a[4]=7;
     i=4;
     x=11;
     while(x<aa+1)
     {
                   j=2;
                   flag=1;
                   while(j*j<x)
                   {
                    if(x%j==0)
                    {
                     flag=0;
                     break;
                    }
                    j++;
                   }
                   if(flag==1)
                   {
                     a[++i]=x;
                   }
                   x+=2;
     }
     sont=i;
}
void Test()
{
for(i=1;i<=sont;i++) printf("%d\n",a[i]);
// getch();
}

Varun Sharma Re: Why WA in test 2. My code here. Please help me. [1] // Problem 1055. Combinations 6 Apr 2010 14:23

Hi,

Try these test cases:

Test Cases

200000 40000
9011

100000 35000
6109

123456 12345
3892

987654 98765
25861

560011 12000
5255

340999 43560
11372

235000 34001
8723

89340 10000
3123

98112 23
35

4567 456
212

Varun

TheDreamCatcher Re: Why WA in test 2. My code here. Please help me. // Problem 1055. Combinations 1 Dec 2010 13:47

Varun Sharma wrote 6 April 2010 14:23

Hi,

Try these test cases:

Test Cases

200000 40000
9011

100000 35000
6109

123456 12345
3892

987654 98765
25861

560011 12000
5255

340999 43560
11372

235000 34001
8723

89340 10000
3123

98112 23
35

4567 456
212

Varun

N M between 1 & 50 000

And IV <TOP SECRET> 15 лет колоний и лагерей будет [2] // Problem 1055. Combinations 29 Jun 2007 21:05

rongyan why I get crash(access violation) at test 6? [5] // Problem 1055. Combinations 13 Sep 2006 18:15

Phan Hoài Nam - Đại học Ngoại ngữ Tin Học TP.HCM The algorithm for solving this problem. EASY TO UNDERSTAND ! [1] // Problem 1055. Combinations 5 Feb 2009 09:07

Rasul please give me some tests. [1] // Problem 1055. Combinations 26 Oct 2009 16:13

Shyu SeiMin WA#3 // Problem 1055. Combinations 17 May 2009 11:55

Vasil Todorov I have a misstake pls help! // Problem 1055. Combinations 19 Feb 2009 02:06

Valentin Baltadjiev Need help. Solution too slow. Code included // Problem 1055. Combinations 19 Feb 2009 01:13

ooo help me!!!!!! // Problem 1055. Combinations 14 Dec 2008 16:08

ooo where is my mistake? // Problem 1055. Combinations 8 Dec 2008 21:10

Gerasim Petrov Velchev My Solution is SUPER! // Problem 1055. Combinations 24 Jul 2008 15:25

Vlad Ionescu How can I sol;ve this faster? [2] // Problem 1055. Combinations 10 Jun 2003 02:16

My program run in 0.741 seconds and i saw most people only needed
0.09s. How can i solve this any faster?

var d:array[1..50000] of integer;
    n,m,i,j,k:longint;
begin
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=m+1 to n do begin
      k:=i;
      for j:=2 to trunc(sqrt(k)) do
          while k mod j=0 do begin
                inc(d[j]); k:=k div j;
                end;
      if k<>1 then inc(d[k]);
      end;
for i:=1 to n-m do begin
      k:=i;
      for j:=2 to trunc(sqrt(k)) do
          while k mod j=0 do begin
                dec(d[j]); k:=k div j;
                end;
      if k<>1 then dec(d[k]);
      end;
k:=0;
for i:=2 to n do
      if d[i]>0 then inc(k);
writeln(k);
end.

Evil Cheater Re: How can I sol;ve this faster? [1] // Problem 1055. Combinations 10 Jun 2003 20:41

> My program run in 0.741 seconds and i saw most people only needed
> 0.09s. How can i solve this any faster?
>
> var d:array[1..50000] of integer;
>     n,m,i,j,k:longint;
> begin
>   fillchar(d,sizeof(d),0);
>   readln(n,m);
>   for i:=m+1 to n do begin
>       k:=i;
>       for j:=2 to trunc(sqrt(k)) do
>           while k mod j=0 do begin
>                 inc(d[j]); k:=k div j;
>                 end;
>       if k<>1 then inc(d[k]);
>       end;
>   for i:=1 to n-m do begin
>       k:=i;
>       for j:=2 to trunc(sqrt(k)) do
>           while k mod j=0 do begin
>                 dec(d[j]); k:=k div j;
>                 end;
>       if k<>1 then dec(d[k]);
>       end;
>   k:=0;
>   for i:=2 to n do
>       if d[i]>0 then inc(k);
>   writeln(k);
> end.
>

SkorKNURE Re: How can I sol;ve this faster? // Problem 1055. Combinations 26 Apr 2008 21:07

0.001s, 336kb.
Use following fact from the number theory:
Power of each prime in binomial coefficient's factorization equals to the number of borrows in the substraction n-k in base p. Iterate all primes less then N and count it if prime will greater then 0;

Viktor what is problem in my programmmmmmmmmmmmmmmmm // Problem 1055. Combinations 4 Jan 2008 17:13

Chojin My C code submited as C++ ,then got "complilation error"?why? // Problem 1055. Combinations 5 Oct 2007 09:40

Orshanskiy Sergey :) [3] // Problem 1055. Combinations 4 Nov 2002 05:39

xcheng Hints for those who got TLE~ // Problem 1055. Combinations 4 Sep 2007 19:46

Discussion of Problem 1055. Combinations