Page 2 of 5

Posted: Sun Nov 16, 2003 9:35 am
by Algoritmo
b3yours3lf wrote:but i've test in my comp (Celeron 1,1 GHZ), it's only take 2 second to find all carmichael number < 65000, but when i submitted itu (only the function to find carmichael number) i got TLE.
You may get TLE if you are calculating carmichael number function again and again for each input. You should use such function just once, generating all carmichael numbers before reading any input. This may look like pre-calculating, but it is not :)
Else, I read you may have problems if you use signed int (4 bytes), because 32 bits are needed to avoid overflow when calculating 65000 * 65000, so you need unsigned long (4 bytes, 32 bits) or long long (8 bytes, 63 bits + 1 bit for signal) types.

Hope I have helped, but now I need your help :)
How did you make such function? I failed to do it. Reading about carmichael numbers in mathworld didn't help either:
http://mathworld.wolfram.com/CarmichaelNumber.html

In my first attempt, I first tested if it is prime. If it is not, I test for all number 2<a<n if the equation "a^n mod n = a" is satisfied, but this would obviously cause overflow.
Please explain to me how to test if a number is Carmichael. You may send you function to murilop@email.iis.com.br :)

How to solve 10006

Posted: Wed Dec 17, 2003 11:00 pm
by backslashnull
Hi there!
for testing the a^n %n==a statement you can use the divide method like this:

[cpp]
unsigned long int bigmod(unsigned long int a,unsigned long int b,unsigned long int c){
if (b==0)
return 1;
else if (b==1)
return a%c;
else if (b%2==0){
int k=bigmod(a,b/2,c)%c;
return (k*k)%c;
}
else return ((bigmod(a,b-1,c)%c)*(a%c))%c;
}
[/cpp]
and you can use the traditional loop for prime check in this way you can solve the problem in O(n*n^1/2*lg(n)) but the real time is much much less.

I got AC in 0.650 seconds even with precalc!maybe the input file size is bigger than 1MB !
beacuse i used a loop like this : while (n!=0) { if n==561 || n==1105 ||n==1729 ...)


Happy AC everyone ! :wink: :lol:

10006 -- peculiar compile error...please help!

Posted: Mon Feb 23, 2004 11:38 pm
by fangs404
my code runs wonderfully on my system, but for some reason, the judge isn't accepting my solution; of all things it gives me a compile error. here's the error:

gcj: Internal compiler error: program jc1 got fatal signal 11

i'm using java, and i'm sending it via the e-mail submitter. there are no text wraparounds, and i'm not trying to access methods that java 1.4.2_03 doesn't have over 1.1. of course, when i submit it, i'm change public class Main to class Main, so that's not the problem either. does anyone have any ideas as to what the problem is and how i can solve it? i can post my code if need be, so just ask if i should. thanks for any and all help.

10006 Time Limit Exceeded .. huh?

Posted: Wed Feb 25, 2004 10:40 pm
by OutCaster
Hey guys

I've tried two ways .. precalculating and storing the numbers in an array .. and then i've tried calculating while the online judge spits out a number .. both have failed

I get time limit exceeded even though it runs on my in less than 10 seconds .. any thoughts?

Thanks

Posted: Thu Feb 26, 2004 1:49 am
by fangs404
well, i fixed it. it turns out that i wasn't checking to see if the input from the console would be null (although this shouldn't cause a compile error at all), but whatever. it works now.

10006

Posted: Wed Mar 10, 2004 11:37 am
by Salmin Sultana
i can't understand why it is wa?
[cpp]
what a funny mistake
[/cpp]

Posted: Wed Mar 10, 2004 12:55 pm
by shamim
consider this line from your code.

[cpp]printf("The number %ld is a Carmichel number.\n",num);
[/cpp]

Here is the first line of sample output:
The number 1729 is a Carmichael number.
I guess you now know the mistake. :wink:

Posted: Wed Mar 10, 2004 1:14 pm
by alu_mathics
The code i used for 10006 gives me TLE.
So i precalculate it .
I wanna know is there a better logic to avoid TLE.

Try this.

Posted: Wed Sep 08, 2004 7:36 am
by _.B._

Posted: Sun Oct 10, 2004 9:19 pm
by purinflash
How did you guys generate the carmichael numbers?

Posted: Sun Oct 17, 2004 8:34 pm
by Noim
i precalcuate the prime but did not precalculate the charmical number . i check every time. it is Accepted but it takes large time 1.450 sec.

when i got n , i check whether it is prime or not. next check from 2 to n-1 if i got any other answer than a^n mod n= a, i break the loop. to calculate a^n mod n , i use calculate a^1, a^2, a^4 , a^8.. (mod n) and with this i make a^n mod n.

i don't know if there is other good procedute other than precalculating or sending data table.

Plz Help me...

Posted: Wed Jun 22, 2005 10:24 am
by J&Jewel
Here is my code I do not understand why this out Wrong Ans:..Plz Help me.....
#include<stdio.h>
int main()
{
int i;
long input,array[15]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973};
while(scanf("%ld",&input)==1)
{
if(input==0) break;
int k=0;
for(i=0;i<=14;i++)
{
if(input==array)
{
printf("The number %ld is a Charmichael number.\n",input);
k++;
break;
}
}
if(k==0) printf("%ld is normal.\n",input);
}
return 0;
}

Posted: Thu Jun 23, 2005 9:41 am
by J&Jewel
Any body plz help me to find the mistake of my code....I m really unable Why.......

linear time

Posted: Sat Aug 06, 2005 10:27 am
by rob
Hi Guys!

Can anybody solve this problem in linear time? I only find this algorithm:

Code: Select all

prev_mod = 2%n;
is_charmich = 0;

for(a=2; a<n; a++){
  prev_mod = a%n;
  for(i=1; i<n; i++){
    prev_mod = (a*prev_mod)%n;
  }

  if(prev_mod != a){
    is_charmich = 0;
    break;
  }

  if(a<sqrtn && !(n%a)){
    is_charmich = 1;        
    break;
  }
}
but it use O(n^2) time. What is the trick of this problem?

rob

(sorry for my terrible english :oops: )

Re: Plz Help me...

Posted: Sat Aug 06, 2005 11:25 am
by rob
Hi!
J&Jewel wrote:Here is my code I do not understand why this out Wrong Ans:..Plz Help me.....
Maybe you should declare k near i (outside the while loop).

It's just an idea, so maybe work or maybe not.

rob