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

M.Z
New poster
Posts: 3
Joined: Sat Jul 20, 2002 4:48 am

10006 - Carmichael Numbers

Post by M.Z » Sat Jul 20, 2002 4:55 am

I got wrong answer. Anyone can help me about this!
Thank you very much!

Code: Select all

[cpp]
/*

#include<iostream.h>

#include<fstream.h>
ofstream out("es_10006.out");

int notprime[65000];
int prime[6505];
int num[100];

int cal(int a,int k,int n)
//return a^k(mod n)
{
  int ans=a;
  if(k==1) return a;
  if(k%2){
	 return (a*cal((a*a)%n,k/2,n))%n; 
  }else{
	 return cal((a*a)%n,k/2,n);
  }
}

void main()
{
  int tot;
  int i,j;
  for(i=1;i<65000;i++) notprime[i]=0;
  prime[0]=2;
  tot=1;
  for(i=3;i<65000;i+=2){
	  if(!notprime[i]){
	     prime[tot++]=i;
		 for(j=3;j<=65000/i;j+=2){
		    notprime[i*j]=1;
		 }
	  }
  }
 
  int n,a;
  tot=0;
  for(n=3;n<65000;n++){
	  if(!notprime[n]) continue;
	  for(a=2;a<n;a++){
	    if(cal(a,n,n)!=a) break; 
	  }
	  if(a==n) num[tot++]=n; 
  }

  out<<tot<<endl;
  for(i=0;i<tot;i++){
     out<<num[i]<<endl;
  }
}

*/

#include<iostream.h>
int num[11]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041};
void main()
{
  int n;
  int i;
  while(1){
	 cin>>n;
	 if(!n) break;
     for(i=0;i<11;i++) if(num[i]==n) break;
	 if(i==11) cout<<n<<" is normal."<<endl;
	 else cout<<"The number "<<n<<" is a Carmichael number."<<endl;
  }
}
[/cpp]

DailyByte
New poster
Posts: 4
Joined: Sat Jul 20, 2002 12:54 pm

Post by DailyByte » Sat Jul 20, 2002 1:02 pm

Change "int" to "unsigned", and you'll get it.
There're 15 numbers totally instead of 11.

oracle
New poster
Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm

Post by oracle » Tue Sep 17, 2002 6:26 pm

I've already found out 15 Carmichael numbers which are <65000

THey are :
561,
1105,
1729,
2465,
2821,
6601,
8911,
10585,
15841,
29341,
41041,
46657,
52633,
62745,
63973

But my program stil getl wrong answer. Can you check for me if above numbers are correct ?[/cpp]

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Wed Sep 18, 2002 4:03 am

yes, it's correct.
about WA, i'm not really sure, but _i think_ there may be more than one number in a single line, lot of leading blanks, and so on. Maybe you could try that.

Code: Select all

     20934                 234           21
19238                                             1203

123            21903                                               6601
                  10585


313         41          5            52633
                                                                               0

oracle
New poster
Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm

Post by oracle » Wed Sep 18, 2002 8:13 am

Thank you to help me to concentrate on other part. I finnaly found out the problems, it's when I send problem using Yahoo Mail, it cut down the long line which contain 'printf()', so the output format have been changed unknowingly.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

MILLION THANKS

Post by stcheung » Tue Nov 19, 2002 8:07 am

THANKS SO MUCH to the person who suggested using unsigned instead of int. My previous program got WA and used as much as 9seconds. After changing all int to unsigned, it got ACCEPTED and even finished with 1.6 seconds, which is still slow compared to other authors' submissions. But this unsigned thingy is exactly the kind of killer bug for me...I swear I would never think the int is the problem. Many thanks again.

beska
New poster
Posts: 2
Joined: Thu Mar 13, 2003 2:10 am

Post by beska » Thu Mar 13, 2003 2:19 am

Ok...I've given up on this. What on earth is going on with this problem? I wrote the program, and got it to run on my machine, but whenever I submitted it it timed out. I eventually got to the point where, after optimizing until the cows came home, wondered if I was even getting the right answer...so I just wrote a short program that just hard codes the few Carmichael numbers in, and prints out the appropate string. When I submitted it, it passed...after 2.5+ CPU seconds! That's 1/4 of the time right there with basically *no* computation. How on earth do people manage to get this to run in 10 CPU seconds, when a program with no computation takes 1/4 of the time by itself?

FlareCDE
New poster
Posts: 3
Joined: Fri Mar 21, 2003 6:31 pm
Location: New York
Contact:

Post by FlareCDE » Fri Mar 21, 2003 6:33 pm

What language are you using? I have heard of a lot of people having problems with Java, even hard coding it (cheating :) ). I used C++ and it was a lot swifter.

And thanks to this thread I finally got it, dunno why I didn't think of changing all my ints to unsigned in the first place.
- Flare Araxion

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

Post by WanBa » Fri May 09, 2003 2:59 am

can anyone tell me why there is a bug when using " int ",and how it is dissipated by superseding with " unsigned" ?? :roll:


best regards angone lend me hand
destiny conditioned by past

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Mon Sep 15, 2003 11:48 pm

That's a good question for Revilla :-)
[]s
Mauricio Oliveira Carneiro

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

10006 help please

Post by nikhil » Wed Oct 08, 2003 3:25 pm

i got this ac
but before i had to generate the car numbers
is there any better procedure???????????????
there are 2 extra numbers at the end of the array before 0
help me please...

#include<stdio.h>

long a,ar[]={561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973,75361,0};

int main(void){
int x, found;

while(1==scanf("%ld", &a) && a){
for(found=x=0;ar[x];x++)
if(a==ar[x]){
printf("The number %ld is a Carmichael number.\n", a);
found=1;
break;
}
if(!found)
printf("%ld is normal.\n", a);
}
return 0;
}

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

10006 Time Limit Exceeded

Post by b3yours3lf » Sat Oct 18, 2003 9:20 am

is there a way to solve this problem without precalculate ?

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

Post by shamim » Sat Oct 18, 2003 9:52 am

I guess so, because even by submitting precalulateed result, I could not solve it in 0 seconds, infact no one has done so yet.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Sat Oct 18, 2003 10:18 am

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.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Sat Nov 01, 2003 3:22 pm

Hey people. Don't you know that a*a when a>sqrt(maxlongint) causes overflow with int????
_____________
NO sigNature

Post Reply

Return to “Volume 100 (10000-10099)”