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

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

Post by czar » Tue Jun 24, 2003 7:27 pm

Nevermind, I found the problem

raiku
New poster
Posts: 2
Joined: Sun Sep 14, 2003 5:29 pm
Location: Spain

10139 - Factovisors

Post by raiku » Sun Sep 14, 2003 5:40 pm

Hi! Can someone tell me why i'm gettin a WA? Which kind of input I fail?

Thanks

[cpp]

#include <stdio.h>

#include <math.h>
#include <iostream>

#define MAX 46400

int sieve[MAX], primers[5000];

using namespace std;

long n, d, d2;


int fer_primers(void)
{
int i, j, z=1;
int s=0;

for(i=0; i<MAX; i++)
sieve=1;
sieve[0]=0;
sieve[1]=0;
primers[0]=2;

for(i=4; i<MAX; i=i+2)
sieve=0;
for(i=3; i<MAX; i=i+2)
if(sieve==1)
{
primers[z]=i;
z++;
for(j=2*i; j<MAX; j=j+i)
sieve[j]=0;
}
return z;
}



int main(int argc, char *argv[])
{
bool div;
int h, k, r, num;
int a=0, q=0, b=0, w=0;
unsigned long u;
int nprimers;

nprimers=fer_primers();



while(cin>>n>>d)
{
d2=d;
if(d==0) div=false;
else if(d==1) div=true;
else if(n==1) div=(d==1);
else if(d<=n) div=true;
else
{
div=true;
h=0;
r=0;
k=2;

while(r<nprimers && div && d>1)
{
k=primers[r];
h=0;
while(d%k==0)
{
h++;
d=d/k;
}

num=0;
u=k;
while(u<n && num<h)
{
num=num+(n/u);
u=u*k;
}
if(num<h) div=false;
r++;
}

if(d>1) div=false;
}
div? cout<<d2<<" divides "<<n<<"!"<<endl: cout<<d2<<" does not divide "<<n<<"!"<<endl;
}

return 0;
}

[/cpp]

koodeGuru
New poster
Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

cannot handle large values.

Post by koodeGuru » Fri May 07, 2004 8:16 pm

I tested your program for some huge fact values and it does not work
1009 1000
1000 divides 1009!
1000 1009
1009 does not divide 1000!
>>1073741824 1000000
>>1000000 divides 1073741824!
Actualy it should be 1000000 does not divide 1073741824! which is very obvious. Even I am having some problems handling large factorials. Your program can actualy handle 1000! which is good. Mine does not even handle 500! How sad :cry:
Someone help.Thanks.

Code: Select all

Java rules

koodeGuru
New poster
Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

10139-Factovisors using BigInteger

Post by koodeGuru » Fri May 07, 2004 9:20 pm

Here is my code for this problem:

Code: Select all

import java.io.*;
import java.util.*;
import java.math.*;

class Main
{
	public static void main(String []args)
	{
		Main code=new Main();
		code.execute();
	}
	
	void execute()
	{
		String s;
    	StringTokenizer st;
    	BigInteger i, j;
		
		while ((s = Main.readLn(255)) != null) 
    	{
	      st = new StringTokenizer(s);
	      i = BigInteger.valueOf(Integer.parseInt(st.nextToken()));
	      j = BigInteger.valueOf(Integer.parseInt(st.nextToken()));
	      factovisor(i,j);
	    }
	}
	
	static String readLn (int maxLg) 
	{
    	byte lin[] = new byte [maxLg];
    	int lg = 0, car = -1;
    	//String line = "";
 
    	try 
    	{
      		while (lg < maxLg) 
      		{
        	car = System.in.read();
        	if ((car < 0) || (car == '\n')) break;
        	lin [lg++] += car;
       		}
    	}
    	catch (IOException e) 
    	{ return (null); }
 
    	if ((car < 0) && (lg == 0)) return (null);
    	return (new String (lin, 0, lg));
  	}
  	
  	void factovisor(BigInteger i, BigInteger j)				//i=n and j=m;
  	{
  		BigInteger facti= BigInteger.valueOf(1);
  		//System.out.println(fact(i).toString());
  	 	for (int k = 2; k <= i.intValue(); k++) 
  	 	{
               BigInteger num = BigInteger.valueOf(k);
               facti = facti.multiply(num);
        }

  		if(facti.mod(j).intValue()==0)
  		System.out.println(j+" divides "+i+"!");
  		else
  		System.out.println(j+" does not divide "+i+"!");
  	}
  	
 }
It is taking a lot of time to calculate large factorial values. How do I minimize that? Thanks. :(

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon May 10, 2004 5:29 am

Are u sure that
1000000 does not divide 1073741824! .
I mean 1073741824 is larger than 1000000, therefore 1073741824! has got to be divisiblle by 1000000 :-?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

shamim is right

Post by sohel » Mon May 10, 2004 11:54 am

Hmmm...

I think Shamim is right.. cos my AC program gives
1000000 divides 1073741824! , as it should.

Raiku:

you made a very minor mistake, I just changed one condition and got it AC....

Hint: The change is in this line

[c]
if(d>1) div=false;
[/c]

Hope it helps.

koodeGuru
New poster
Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

o o!

Post by koodeGuru » Tue May 11, 2004 4:52 am

I am sorry for the confusion. I was wrong. [java]Test java[/java][/java]

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Wed Jun 02, 2004 9:10 am

dear htl
consider the case where m has a prime factor which is bigger than Sqrt (2^31).
i think in these cases your code is wrong

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

10139

Post by .. » Fri Jun 04, 2004 7:42 am

I can't find any bug in my old accepted code........
0 doesn't divded any factorial, right?~
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.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Fri Jun 04, 2004 10:09 am

Hi!

0 doesn't divide anything.
(But take care of 0!=1)

After rejudge I got TLE. I rewrote factorization and got AC.
But before I got WA 'cause I outputted "divids" instead of "divides" :roll: - I had been looking for this stupid bug for about half an hour...

Don't you have something like that?

Have AC.
Andrey.

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

10139 WA after rejudgement

Post by WR » Fri Jun 04, 2004 1:08 pm

Hello,

after the rejudgement my program gets a WA.
Could anybody please verify the following data?

input:

Code: Select all

0 0
1 0
2 0
10 0
2147483647 0
0 1
1 1
2 1
10 1
2147483647 1
10 2
2147483647 2
10 3
5 5
6 9
0 10
6 18
6 27
1009 1000
1000 1009
20 10000
20 100000
1073741824 1000000
43213 93390991
123456789 123456871
123456789 123456873
123456789 123456790
123456789 124880621
123456789 124925329
43213 906190609
1073741824 1073741824
2147483647 1073741824
0 2147483647
1 2147483647
2 2147483647
1073741824 2147483647
2147483647 2147483647
output:

Code: Select all

0 does not divide 0!
0 does not divide 1!
0 does not divide 2!
0 does not divide 10!
0 does not divide 2147483647!
1 divides 0!
1 divides 1!
1 divides 2!
1 divides 10!
1 divides 2147483647!
2 divides 10!
2 divides 2147483647!
3 divides 10!
5 divides 5!
9 divides 6!
10 does not divide 0!
18 divides 6!
27 does not divide 6!
1000 divides 1009!
1009 does not divide 1000!
10000 divides 20!
100000 does not divide 20!
1000000 divides 1073741824!
93390991 divides 43213!
123456871 does not divide 123456789!
123456873 divides 123456789!
123456790 divides 123456789!
124880621 divides 123456789!
124925329 divides 123456789!
906190609 does not divide 43213!
1073741824 divides 1073741824!
1073741824 divides 2147483647!
2147483647 does not divide 0!
2147483647 does not divide 1!
2147483647 does not divide 2!
2147483647 does not divide 1073741824!
2147483647 divides 2147483647!
Many thanks in advance!

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Fri Jun 04, 2004 9:12 pm

helo WR!

I checked your output and found nothing wrong,
so you may use the following random io
(only the input random:))

http://morse.inf.unideb.hu/~noszaly/xxx ... _10139.tgz

Peace,
Csaba Noszaly
Last edited by tat tvam asi on Mon Oct 18, 2004 7:02 pm, edited 1 time in total.

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

Post by .. » Sat Jun 05, 2004 5:36 am

Thanks for the in/out, but I get the same output........
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.

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

Post by WR » Mon Jun 07, 2004 7:20 am

To tat tvam asi:

Thanks for the data. My program returns absolutely the same output!

So what could now be the problem??!!

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

Post by alu_mathics » Mon Jun 07, 2004 10:11 am

After rejudge i get w.a. I change all the long data into long long and finally got A.C.
cuii e

Post Reply

Return to “Volume 101 (10100-10199)”