10484 - Divisibility of Factors

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10484 - Divisibility of Factors

Post by Hisoka » Tue Apr 29, 2003 8:20 pm

Hello....

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

Thanks....

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

Post by Hisoka » Tue Apr 29, 2003 8:31 pm

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Apr 30, 2003 8:10 am

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

Post by Hisoka » Wed Apr 30, 2003 8:14 am

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:

Post by turuthok » Wed Apr 30, 2003 8:16 am

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:

Post by Dominik Michniewski » Wed Apr 30, 2003 8:47 am

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:

Post by turuthok » Wed Apr 30, 2003 9:42 am

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:

Post by Dominik Michniewski » Wed Apr 30, 2003 11:37 am

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?

Post by Tomson » Wed Apr 30, 2003 8:18 pm

: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]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Apr 30, 2003 9:11 pm

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

Post by Tomson » Thu May 01, 2003 8:05 am

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]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu May 01, 2003 8:20 am

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

Post by Tomson » Thu May 01, 2003 9:07 am

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:

Post by turuthok » Thu May 01, 2003 10:31 am

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

Post by Tomson » Thu May 01, 2003 1:10 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[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]

Post Reply

Return to “Volume 104 (10400-10499)”