Page **1** of **1**

### 10325 - The Lottery

Posted: **Sat Jul 13, 2002 6:31 pm**

by **20571KJ**

I had a solution but it's too slow.

If you don't mind, please help me....show me a better one ???

Thank you.

Posted: **Sun Jul 14, 2002 2:52 pm**

by **Christian Schuster**

Hi,

I did it the following way:

- set the initial "result" value to n.

- compute the lcm of every subset of divisors (except the empty one)

- if the size of a subset it odd, subtract n/lcm from "result"

- if it is even, add n/lcm to "result"

Those operations can be done in an iteration loop, doing some bit manipulation and lcm(a,b)=a*b/gcd(a,b).

I got AC in 270ms, but I don't know how to reach 20ms. That seems incredible!

### WA...help me please !!!!!

Posted: **Sun Jul 14, 2002 6:32 pm**

by **20571KJ**

I try to do this problem. I found a very special DP. I think that I was right.

Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??

(I use TP7)

[pascal]

const fi = 'lottery.in';

fo = 'lottery.out';

type

tab1 = array [1..15] of longint;

var

S: tab1;

max, n, i: longint;

function UCLN(a, b: longint): longint;

begin

if a mod b = 0 then UCLN := b

else UCLN := UCLN(b, a mod b);

end;

function F(Num: tab1; n: byte; Max: longint): longint;

var

j, i, k: longint;

S: tab1;

begin

if n = 1 then F := Max div Num[1]

else

begin

j := 0;

for i := 1 to N-1 do

begin

k := round(Num* / UCLN(Num**, Num[n]));*

if (j = 0) or (S[j] <> k) then

begin

j := j + 1;

S[j] := k;

end;

end;

F := F(Num, n-1, Max) + Max div Num[n] - F(S, n-1, Max div Num[n]);

end;

end;

begin

assign(input, fi); reset(input);

assign(output, fo); rewrite(output);

read(max);

read(n);

for i := 1 to n do read(s*);*

writeln(Max - F(S, n, Max));

close(input); close(output);

end.[/pascal]

### WA...help me please !!!!!

Posted: **Sun Jul 14, 2002 6:33 pm**

by **20571KJ**

I try to do this problem. I found a very special DP. I think that I was right.

Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??

(I use TP7)

[pascal]

const fi = 'lottery.in';

fo = 'lottery.out';

type

tab1 = array [1..15] of longint;

var

S: tab1;

max, n, i: longint;

function UCLN(a, b: longint): longint;

begin

if a mod b = 0 then UCLN := b

else UCLN := UCLN(b, a mod b);

end;

function F(Num: tab1; n: byte; Max: longint): longint;

var

j, i, k: longint;

S: tab1;

begin

if n = 1 then F := Max div Num[1]

else

begin

j := 0;

for i := 1 to N-1 do

begin

k := round(Num* / UCLN(Num**, Num[n]));*

if (j = 0) or (S[j] <> k) then

begin

j := j + 1;

S[j] := k;

end;

end;

F := F(Num, n-1, Max) + Max div Num[n] - F(S, n-1, Max div Num[n]);

end;

end;

begin

assign(input, fi); reset(input);

assign(output, fo); rewrite(output);

read(max);

read(n);

for i := 1 to n do read(s*);*

writeln(Max - F(S, n, Max));

close(input); close(output);

end.[/pascal]

Posted: **Tue Jul 16, 2002 9:37 pm**

by **Joe Smith**

A few things, dunno if these will help:

1. Shouldn't you be reading from stdin/stdout instead of those files? (I don't know, I don't use Pascal for my solutions.)

2. Your algorithm doesn't look correct to me, but I don't think I really understand what you're trying to do in it. There was a good hint above... if that doesn't help, here's the meat of my solution (in C):

[cpp]

int div(int sign, int m, long long val) {

if (val>N) return 0;

if (m==M) return sign*(N/val);

return div(sign,m+1,val) + div(-1*sign,m+1,lcm(val,nums[m]));

}

[/cpp]

3. Watch out for integer overflow (each of the numbers can be up to 2^31-1).

Posted: **Wed Jul 17, 2002 4:41 am**

by **20571KJ**

I did solve this problem. My program run in 0.13s.

But I see that someone can run in 0.02s.

That's great. Anyone know how ??

Ah.., here is my program.

I used Dynamic Programing. But, it's very special ???

[pascal]

type

tab1 = array [1..15] of integer;

var

S: tab1;

max, n, i: integer;

function UCLN(a, b: integer): integer;

begin

if a mod b = 0 then UCLN := b

else UCLN := UCLN(b, a mod b);

end;

function F(Num: tab1; n, Max: integer): integer;

var

j, i, k: integer;

S: tab1;

begin

if n = 1 then F := Max div Num[1]

else

begin

j := 0;

fillchar(S, sizeof(S), 0);

for i := 1 to N-1 do

begin

k := Num* div UCLN(Num**, Num[n]);*

if (j = 0) or (S[j] <> k) then

begin

j := j + 1;

S[j] := k;

end;

end;

F := F(Num, n-1, Max) + Max div Num[n] - F(S, j, Max div Num[n]);

end;

end;

begin

while not Eof(input) do

begin

readln(max, n);

for i := 1 to n do read(s*);*

readln;

writeln(Max - F(S, n, Max));

end;

end.

[/pascal]

Posted: **Wed Jul 17, 2002 9:47 am**

by **Adrian Kuegel**

Have you thought about input like:

20 4

2 4 6 8

It is the same as

20 1

2

If you remove the numbers that are not needed you will improve your runtime.

### 10325 Lottery - W.A.

Posted: **Tue Aug 20, 2002 7:33 am**

by **tokei**

I am gonna go nuts because of this problem....

I got W.A 12 times.....

Can anyone give me some test cases to help me?

Thanks in advance.

Posted: **Tue Aug 20, 2002 12:21 pm**

by **Adrian Kuegel**

It is probably the same mistake I did during contest.

Try this input:

20 2

4 6

Output:

13

Posted: **Tue Aug 20, 2002 8:14 pm**

by **tokei**

Actually, my program produces the correct answer for the above test case. However, I still do not understand why my program could not get accepted. >_<

Here is my code:

[cpp]

#include <stdio.h>

#include <math.h>

long long int save[100],used[100],num[100];

long long int result,m,n;

long long int gcd(long long int a,long long int b)

{

if(a%b==0) return b;

else return gcd(b,a%b);

}

void DFS(int k,int depth,int next) // find subset...

{

int i;

if(depth==k) {

long long int g,l,tmp;

int j;

g = save[0];

l = save[0];

for(j=1;j<depth;j++) {

g = gcd(g,save[j]);

}

for(j=1;j<depth;j++) {

l*=save[j];

if(l/g > n) { break; }

}

l/=g;

if(k%2)

result -= n/l;

else

result += n/l;

}

for(i=next;i<m;i++) {

if(!used*) {*

used*=1;*

save[depth] = num*;*

DFS(k,depth+1,i+1);

used*=0;*

}

}

}

void check()

{

int flag=1;

int i,j,mov;

while(flag) {

flag=0;

for(i=0;i<m;i++) {

for(j=i+1;j<m;j++) {

if(num*%num[j]==0||num[j]%num**==0) {*

if(num*>num[j])*

mov = i;

else

mov = j;

flag=1;

break;

}

}

if(flag) break;

}

next:

if(flag) {

for(i=mov;i<m;i++)

num* = num[i+1];*

m--;

}

}

}

int main()

{

int k,i,j;

while(scanf("%lld %lld",&n,&m)!=EOF) {

for(i=0;i<m;i++) {

scanf("%lld",&num*);*

}

check(); // find if there exists a case such that 2,4,8,16....

for(k=0;k<=m;k++)

used[k]=0;

result = n;

for(k=0;k<m;k++)

result -= n/num[k];

for(k=2;k<=m;k++)

DFS(k,0,0);

printf("%lld\n",result);

}

return 0;

}

[/cpp]

### 10325 why WA !!!

Posted: **Fri May 09, 2003 2:36 am**

by **Dmytro Chernysh**

My program does passes all test cases in the forum and the test cases that AC program that is posted in the forum, but why WA?

Can anybody post some trick test cases?[/pascal][/code]

Posted: **Mon Apr 05, 2004 12:11 am**

by **Cosmin.ro**

I had a hard time with large numbers ...

Here is a input:

2000000000 14

1073741789 1073741783 1073741741 1073741723 1073741719 1073741717 1073741689 1073741671 1073741663 1073741651 1073741621 1073741567 1073741561 1073741527

Output:

1999999986

### Test these

Posted: **Mon Mar 28, 2005 11:56 am**

by **Rajib**

Here is some test cases:

**Input:**
100 4

2 3 5 7

20 2

4 6

100 6

2 5 8 30 101 7

2100000000 10

12345 54123 23425 20000 12312 22222 1234 2021 111111 12344321

2147483647 3

2147483647 2 128

**Output:**
22

13

34

2096573927

1073741823

If the above test cases are not enough, you can make your own test case for smaller input range (<1000000) and using ceiv approach you can get the correct solution. Good luck.

### Re: 10325 - The Lottery

Posted: **Wed Nov 24, 2010 1:20 am**

by **ask_1171**

using sieve approach im getting tle.. can any one give me a good algo to do it..

#include<iostream>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

#define MAX 2147483647

unsigned mark[(MAX>>5)+2];

#define checkp(x,n) (x[n>>5]&(1<<(n&31)))

#define setp(x,n) (x[n>>5]|=(1<<(n&31)))

#define resetp(x,n) (x[n>>5]&=~(1<<(n&31)))

int ar[20];

int p;

int n,m;

void sieve()

{

int i,j,k;

p=0;

memset(mark,0,(m/32)*sizeof(unsigned)+2);

for(i=1;i<=m;i++)

for(j=ar*,k=ar**;j<=n&&j>0;j=j+k)*

if(!checkp(mark,j))

{

setp(mark,j);

p++;

}

}

int main()

{

int i;

freopen("1.txt","r",stdin);

while(scanf("%d %d",&n,&m)==2)

{

for(i=1;i<=m;i++)

scanf("%d",&ar*);*

sieve();

printf("%d\n",n-p);

}

return 0;

}

### Re: 10325 - The Lottery

Posted: **Mon Sep 08, 2014 5:11 pm**

by **matrix2220**

**Hint:**

You are given N and M and you have M selected tickets numbered

Tickets from 1 to N should not be divisible by any of the selected tickets

for example if we have a, b, c, ... selected tickets

then any ticket that is divisible by a or b or c or .... or LCM(a,b) or LCM(a,c) or ..... or LCM(a,b,c)

Lets Assume N = 10 and M = 2

Selected = 2 3

Then our numbers from 1 to N should not be divisible by

2

3

LCM(2,3) = 6

Lets see what number those selected numbers divides

List-----------1 2 3 4 5 6 7 8 9 10

Divisible by:---2 2 2 2 2----------------We will exclude(2,4,6,8,10)

Divisible by:-----3 3 3-------------------We will exclude(3,6,9)

Divisible by:----------- 6-----------------------We will exclude(6)

Notice that we excluded "6" 3 times, we need to solve this problem

The solution for that is to determine the size of set of the selected number {2,3}

LCM(2,3) is the LCM of the set {2,3} the size = 2 which is even then we should subtract N/LCM(2,3) from

forbidden count, in case of LCM(2,3) = 6 >>> N/LCM(2,3) = 1 which is what we want to subtract.

In case of the size of the set is odd, we need to add N/LCM(a) to the forbidden count, if set is {2}

then it's size is 1 which is odd then add N/LCM(1,2) to the forbidden count.

The reason for that is, if you have an even set then the product of it's numbers is excluded previously

more than once, so we need to subtract it to avoid redundant so that we excluded it those numbers only once.