10484 - Divisibility of Factors

[Hisoka]

Hello....

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

Thanks....

[Hisoka]

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

[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

[Hisoka]

hello.....

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

Code: Select all

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

[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-

[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

[turuthok]

I sent a reply ... good luck

-turuthok-

[Dominik Michniewski]

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

DM

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

[turuthok]

When n == 0, it's not necessary that the output will always be 0.
0! is divisible by 1 ...

-turuthok-

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

[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-

[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?

[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-

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