10139 - Factovisors

[WR]

A minute ago I changed all the long data into long long and submitted again, still WA!

What's the sense in this ever increasing data range anyway?

But ok, the random file that tat tvam asi mentioned contains more than 16000 input lines and if the output is ok (I hope so!) and my program returns the same output, what else could be wrong?!

Found the bug!

My compiler isn't too strict with format specifiers. For the OJ I forgot to change "ld" into "lld".

Thanks tat tvam asi and alu_mathics!

ps: Has anybody an example that works with long long but doesn't with (unsigned) long and is within the problem's stated data range?

[..]

I get the problem solved also.........
I get WA because of a small bug.
It will be shown if I use the input for all m, n < 100,
but I only think about big input...........

[alu_mathics]

For my w.a. solution i have to change the long data into long long.
Formula:
The number of occurence of a prime factor in n! is
summation (floor(n/pow(f,i))) where i=1,2,3.... and pow(f,i)<=n;
while calculating the value of pow(f,i) my previous code gives data overflow.Do you consider that case?Hope so.

[udvat]

in this problem
n can be a prime number closer to 2^31.
so i have to run sieve for 2^31.
but for this i have to keep an array of length 2^31.it is not supported.what can I do?plz help me.

[UFP2161]

In order to determine if a number is prime, you only need to check all the prime numbers from two to the square root of that number.

[udvat]

thanx for reply.but i tried it and got TLE.
I am telling my idea here,plz tell me where is the bug

input:m & n is given
output:i have to determine whether m divides n!

my idea:

if(m==0) ....................then NO
if(n==0 || n==1)
{
if(m==1).................YES
else.........................NO
}
if(m<=n)................. YES
if(m> n and m is prime)..........NO

otherwise:
I take n,calculate gcd(m,n),divides m with gcd,
if m>1,then take n-1,calculate gcd(m,n-1),divides m with gcd.
if m>1 then take n-2 & so on,if m becomes 1 then stop.n will be reduced
to 2 if m is always >1.

m & n can be 2^31 & my code consumes time when it checks whether
m or n is prime when m or n is closer to 2^31.

I am tired of getting TLE,help me plz.

[rajsekar_manokaran]

You need not construct the sieve upto 2^31.
It is enough if you construct a sieve to sqrt(2^31) and store the primes in an array.

Now if the number is composite, one factor will surely be in the array
so do whatever is required for each factor by looping through the array.
and divide by the factor
if the number if still not 1 then it is some prime greater than sqrt(2^31)
so handle that case explicitly.

[Minilek]

uvdat: from the description of your algorithm I'm not sure where you even use primality. also, it seems like ur algorithm is way too slow.

i forgot which was m and which was n, but let's say we're trying to figure out whether m divides n!.

now looking at ur algorithm...suppose m is a very large prime (let's say m is the first prime greater than 2147483647/2). Now let's say we run your algorithm with n = 2147483647. Then the gcd you calculate in your algorithm will be 1 for a LONG LONG time (over a billion runs) until we finally decrement n enough to get to m (since m is prime and m*2 is bigger than the max input). this would give you TLE.

i'll give you a hint as to a better way to do it:

hint: if m = p_1^k_1 * p_2^k_2 * ... *p_r^k_r (each p_i is a prime),
then how do we know if m divides n!
??

[nesqi]

Could someone post more test data for this problem?

This is the test data I have tested on so far:

Input:

0 1
1 1
2 1
3 6
1233473 1233473
46337 2144430863
2144430862 2144430863
12 479001600
12 43545600
12 6220800
12 467775
12 248832
12 42525
12 1925
12 1215
12 1024
12 243
12 77
12 25
12 11
12 7
12 2048
12 729
12 125
12 121
12 49
1 2
2 3
0 2
0 1233473
1233472 1233473


Output:

1 divides 0!
1 divides 1!
1 divides 2!
6 divides 3!
1233473 divides 1233473!
2144430863 divides 46337!
2144430863 divides 2144430862!
479001600 divides 12!
43545600 divides 12!
6220800 divides 12!
467775 divides 12!
248832 divides 12!
42525 divides 12!
1925 divides 12!
1215 divides 12!
1024 divides 12!
243 divides 12!
77 divides 12!
25 divides 12!
11 divides 12!
7 divides 12!
2048 does not divide 12!
729 does not divide 12!
125 does not divide 12!
121 does not divide 12!
49 does not divide 12!
2 does not divide 1!
3 does not divide 2!
2 does not divide 0!
1233473 does not divide 0!
1233473 does not divide 1233472!


It looks ok too me. What am I missing??
Are there some tricky cases that I have missed?

[dumb dan]

You seem to have tested quite alot, and they all look ok.
Here are a few more:

input:

Code: Select all

94764610 284293833
94764612 284293833
11 479001600
21471 2147483647
7 32
8 128
8 256

output:

Code: Select all

284293833 does not divide 94764610!
284293833 divides 94764612!
479001600 does not divide 11!
2147483647 does not divide 21471!
32 does not divide 7!
128 divides 8!
256 does not divide 8!

[nesqi]

I found the problem! Thanks allot!

[d91-lek]

For my w.a. solution i have to change the long data into long long.
Formula:
The number of occurence of a prime factor in n! is
summation (floor(n/pow(f,i))) where i=1,2,3.... and pow(f,i)<=n;
while calculating the value of pow(f,i) my previous code gives data overflow.Do you consider that case?Hope so.

I really needed that calm stating of a way to count the occurances. Thank you.
I would like to add that long long is not necessary to avoid overflow. Consider
this overflowing algorithm:

Code: Select all

/* Gives f's occurances in n! */
int multiplicity_in_factorial(int f, int n) {
  int sum = 0, fpot = f;
  while(fpot <= n) {
    sum += n / fpot;
    fpot *= f;
  }
  return sum;
}

Yes I'm very sloppy by using int. My and Valladolid's MAXINT is 2147483647 today.
Anyway, when n = MAXINT, fpot overflows since fpot > MAXINT becomes the loop
stopping criterion.
In order not to multiply fpot with f if the product is greater than MAXINT we just
have to divide MAXINT by f and use that for comparison before we multiply. And
furthermore, we don't need to know MAXINT. n fits in our datatype, no? Well, don't
ever go beyond n.

Code: Select all

/*   Gives f's occurances in n! */
int multiplicity_in_factorial(int f, int n) {
  int sum = 0, fpot = 1;
  int fpotlim = n / f;
  while(fpot <= fpotlim) {
    fpot *= f;
    sum += n / fpot;
  }
  return sum;
}

Totally wrong? A little correct? Please?

[dumb dan]

looks ok as far as I can tell

[Sedefcho]

How do you deal with that problem anyway ?
It says both M and N could be <= 2^31 so we can not
precalculate the primes up to 2^31, this is too high limit.
Any hints about algotihms ?

By the way problem 10780 is basically the
same problem. Check this:
http://acm.uva.es/p/v107/10780.html

But in problem 10780 we have the restirctions:
1<m<5000
0<n<10000
which makes the problem much easier as we can just
precalculate the primes up to a certain limit and then
answer the question if M divides N much easier.

How do you deal with that problem ?
For example if M is some huge prime
( 1 000 000 000 < M < 2147483648 = 2^31 ) ?
How do we attack the problem in that case ?

[Larry]

You don't always need to precalc primes..