10006 - Carmichael Numbers

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

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Sun Nov 16, 2003 9:35 am

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

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm

How to solve 10006

Post by backslashnull » Wed Dec 17, 2003 11:00 pm

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:

fangs404
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am
Contact:

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

Post by fangs404 » Mon Feb 23, 2004 11:38 pm

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.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein

OutCaster
New poster
Posts: 4
Joined: Thu Jan 22, 2004 2:24 am

10006 Time Limit Exceeded .. huh?

Post by OutCaster » Wed Feb 25, 2004 10:40 pm

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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am
Contact:

Post by fangs404 » Thu Feb 26, 2004 1:49 am

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.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

10006

Post by Salmin Sultana » Wed Mar 10, 2004 11:37 am

i can't understand why it is wa?
[cpp]
what a funny mistake
[/cpp]
Last edited by Salmin Sultana on Thu Mar 11, 2004 11:18 am, edited 1 time in total.

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

Post by shamim » Wed Mar 10, 2004 12:55 pm

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:

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

Post by alu_mathics » Wed Mar 10, 2004 1:14 pm

The code i used for 10006 gives me TLE.
So i precalculate it .
I wanna know is there a better logic to avoid TLE.
cuii e

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Try this.

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

_.

purinflash
New poster
Posts: 2
Joined: Sat Nov 22, 2003 1:35 am

Post by purinflash » Sun Oct 10, 2004 9:19 pm

How did you guys generate the carmichael numbers?

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Sun Oct 17, 2004 8:34 pm

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.
__nOi.m....

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Plz Help me...

Post by J&Jewel » Wed Jun 22, 2005 10:24 am

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;
}
I hate Wrong Answer!

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Thu Jun 23, 2005 9:41 am

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

rob
New poster
Posts: 2
Joined: Fri Feb 18, 2005 1:21 pm
Contact:

linear time

Post by rob » Sat Aug 06, 2005 10:27 am

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

rob
New poster
Posts: 2
Joined: Fri Feb 18, 2005 1:21 pm
Contact:

Re: Plz Help me...

Post by rob » Sat Aug 06, 2005 11:25 am

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

Post Reply

Return to “Volume 100 (10000-10099)”