## 10484 - Divisibility of Factors

Moderator: Board moderators

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

### 10484 - Divisibility of Factors

Hello....

Can you give me more sample I/O ?
I always got WA about this problem..... Thanks....

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
Got AC now, I use long long instead of int. Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hello.....

maybe you wrong because of this.
there is negatif input in d.

Code: Select all

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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I sent a reply ... good luck -turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I've got it. Thanks all for help, especially thanks for turuthok )

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

### I always got WA, I don't know why? 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 = {
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;

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]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
When n == 0, it's not necessary that the output will always be 0.
0! is divisible by 1 ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
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 = {
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;

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]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
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?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
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 = {
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;

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]