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..... :cry:

Thanks....

Posted: Tue Apr 29, 2003 8:31 pm
by Hisoka
Got AC now, I use long long instead of int. :oops:

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.

Code: Select all

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

Posted: Wed Apr 30, 2003 8:16 am
by turuthok
I just can think of boundary cases ... remember that n can be 0.

Code: Select all

0 2147483647
100 1
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
:cry: I always got WA, can somebody help me or give me some test cases? Thanks very much! :cry: :cry: :cry:
[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. :cry: :cry: :cry:
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]