10006 - Carmichael Numbers

[Algoritmo]

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

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

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

[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

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

[Salmin Sultana]

i can't understand why it is wa?
[cpp]
what a funny mistake
[/cpp]

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

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

[_.B._]

http://www.comp.nus.edu.sg/~stevenha/pr ... aths1.html

[purinflash]

How did you guys generate the carmichael numbers?

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

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

[J&Jewel]

Any body plz help me to find the mistake of my code....I m really unable Why.......

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

[rob]

Hi!

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