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

### 10484 - Divisibility of Factors

Posted: **Tue Apr 29, 2003 8:20 pm**

by **Hisoka**

Hello....

Can you give me more sample I/O ?

I always got WA about this problem.....

Thanks....

Posted: **Tue Apr 29, 2003 8:31 pm**

by **Hisoka**

Got AC now, I use long long instead of int.

Posted: **Wed Apr 30, 2003 8:10 am**

by **Dominik Michniewski**

Could anyone tell me some special IO for this problem ?

I got WA, and I can send my code if anyone want to help me ...

Best regards

Dominik Michniewski

Posted: **Wed Apr 30, 2003 8:14 am**

by **Hisoka**

hello.....

maybe you wrong because of this.

there is negatif input in d.

Posted: **Wed Apr 30, 2003 8:16 am**

by **turuthok**

I just can think of boundary cases ... remember that n can be 0.

Dominik, you can send me your solution if you want ...

-turuthok-

Posted: **Wed Apr 30, 2003 8:47 am**

by **Dominik Michniewski**

I handle negative values for D because I heve line:

if(D < 0) D = -D;

maybe its incorrect ? I think that's no matter with sign of D

turuthok,, I send you my code .... thanks for help

Best regards

DM

Posted: **Wed Apr 30, 2003 9:42 am**

by **turuthok**

I sent a reply ... good luck

-turuthok-

Posted: **Wed Apr 30, 2003 11:37 am**

by **Dominik Michniewski**

I've got it. Thanks all for help, especially thanks for turuthok

)

DM

### I always got WA, I don't know why?

Posted: **Wed Apr 30, 2003 8:18 pm**

by **Tomson**

I always got WA, can somebody help me or give me some test cases? Thanks very much!

[cpp]

#include <iostream.h>

#include <memory.h>

int primes[26] = {

2,

3,

5,

7,

11,

13,

17,

19,

23,

29,

31,

37,

41,

43,

47,

53,

59,

61,

67,

71,

73,

79,

83,

89,

97,

111 };

int cnt[30];

void main()

{

int n , d;

cin >> n >> d;

while ( n || d ) {

if ( n==0)

cout << 0 << endl;

else {

if ( d<0 )

d = -d;

memset(cnt , 0 , sizeof(cnt));

int i = 0;

while ( primes

* <= n ) {*

int t = primes*;*

while ( t <= n ) {

cnt* += n/t;*

t *= primes*;*

}

i ++;

}

i = 0;

while ( primes* <= n ) {*

while ( d%primes*==0 ) {*

cnt* --;*

d /= primes*;*

}

i ++;

}

if ( d>1 )

cout << 0 << endl;

else {

long long r = 1;

i = 0;

while ( primes* <= n ) {*

if ( cnt* ) *

r *= (long long)(cnt[i] + 1);

i ++;

}

cout << r << endl;

}

}

cin >> n >> d;

}

}

[/cpp]

Posted: **Wed Apr 30, 2003 9:11 pm**

by **turuthok**

When n == 0, it's not necessary that the output will always be 0.

0! is divisible by 1 ...

-turuthok-

Posted: **Thu May 01, 2003 8:05 am**

by **Tomson**

your mean is because 0! equals 1, if n==0, 1 should be outputed but 0,

didn't it?

I modified this bug, but I still got WA.

Why????

[cpp]

#include <iostream.h>

#include <memory.h>

int primes[26] = {

2,

3,

5,

7,

11,

13,

17,

19,

23,

29,

31,

37,

41,

43,

47,

53,

59,

61,

67,

71,

73,

79,

83,

89,

97,

111 };

int cnt[30];

void main()

{

int n , d;

cin >> n >> d;

while ( n || d ) {

if ( n==0)

cout << 1 << endl;

else {

if ( d<0 )

d = -d;

memset(cnt , 0 , sizeof(cnt));

int i = 0;

while ( primes

* <= n ) { *

int t = primes*; *

while ( t <= n ) {

cnt* += n/t; *

t *= primes*; *

}

i ++;

}

i = 0;

while ( primes* <= n ) { *

while ( d%primes*==0 ) { *

cnt* --; *

d /= primes*; *

}

i ++;

}

if ( d>1 )

cout << 0 << endl;

else {

long long r = 1;

i = 0;

while ( primes* <= n ) { *

if ( cnt* ) *

r *= (long long)(cnt[i] + 1);

i ++;

}

cout << r << endl;

}

}

cin >> n >> d;

}

}

[/cpp]

Posted: **Thu May 01, 2003 8:20 am**

by **turuthok**

Don't get me wrong ...

n=0, d=1, output=1 ... (there is only one factor of 0! that is divisible by d)

n=0, d=2, output=0 ... (no factor of 0! that can divide d)

-turuthok-

Posted: **Thu May 01, 2003 9:07 am**

by **Tomson**

turuthok

I've changed my code as

[cpp]

if ( n==0 ) {

if ( d==1 )

cout << 1 << endl;

else

cout << 0 << endl;

}

[/cpp]

but I still got WA.

I don't know why, can you help me?

Posted: **Thu May 01, 2003 10:31 am**

by **turuthok**

Tomson, ... did you try d=-1 ???

I didn't look at the rest of your code, though ... just spotted that particular case.

Good luck,

-turuthok-

Posted: **Thu May 01, 2003 1:10 pm**

by **Tomson**

Oh, My luck is so bad. Yes, I've considered the case that d = -1, but still got WA.

here is my code. I' m so puzzle. can you give me some help?

[cpp]

#include <iostream.h>

#include <memory.h>

int primes[26] = {

2,

3,

5,

7,

11,

13,

17,

19,

23,

29,

31,

37,

41,

43,

47,

53,

59,

61,

67,

71,

73,

79,

83,

89,

97,

111 };

int cnt[30];

void main()

{

int n , d;

cin >> n >> d;

while ( n || d ) {

if ( d<0 )

d = -d;

if ( n==0 ) {

if ( d==1 )

cout << 1 << endl;

else

cout << 0 << endl;

}

else {

memset(cnt , 0 , sizeof(cnt));

int i = 0;

while ( primes* <= n ) {*

int t = primes*;*

while ( t <= n ) {

cnt* += n/t;*

t *= primes*;*

}

i ++;

}

i = 0;

while ( primes* <= n ) {*

while ( d%primes*==0 ) {*

cnt* --;*

d /= primes*;*

}

i ++;

}

if ( d>1 )

cout << 0 << endl;

else {

long long r;

i = 0;

while ( primes* <= n ) {*

if ( cnt* ) *

r *= (long long)(cnt[i] + 1);

i ++;

}

cout << r << endl;

}

}

cin >> n >> d;

}

}

[/cpp]