10139 - Factovisors

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

Moderator: Board moderators

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Mon Jun 07, 2004 11:29 am

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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Jun 07, 2004 1:48 pm

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...........
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Tue Jun 08, 2004 8:24 pm

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.
cuii e

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

10139

Post by udvat » Thu Jul 29, 2004 10:30 am

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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Jul 30, 2004 12:48 am

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
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

getting tle

Post by udvat » Fri Jul 30, 2004 8:25 pm

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
New poster
Posts: 9
Joined: Fri Feb 20, 2004 6:48 am
Location: India
Contact:

Square root sieve

Post by rajsekar_manokaran » Wed Aug 04, 2004 8:38 pm

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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Sun Aug 08, 2004 10:13 am

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
New poster
Posts: 5
Joined: Thu Sep 30, 2004 4:18 pm

10139 Factovisors. WA, need more test data.

Post by nesqi » Sun Oct 03, 2004 7:44 pm

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?

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Mon Oct 04, 2004 6:34 pm

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
New poster
Posts: 5
Joined: Thu Sep 30, 2004 4:18 pm

Post by nesqi » Tue Oct 05, 2004 12:12 am

I found the problem! Thanks allot!

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Wed Oct 06, 2004 10:35 pm

alu_mathics wrote: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?
Last edited by d91-lek on Thu Apr 07, 2005 5:13 pm, edited 1 time in total.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu Oct 07, 2004 1:07 pm

looks ok as far as I can tell

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

algotihm? hints ?

Post by Sedefcho » Mon Feb 21, 2005 12:58 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Mar 03, 2005 11:51 pm

You don't always need to precalc primes..

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest