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

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:

10006-WA why

Post by sohag144 » Thu Apr 13, 2006 6:07 am

Is there anyone to help me.
code deleted.
although it outputs correctly judge says wrong answer.please help. :cry:
Last edited by sohag144 on Sat Apr 15, 2006 2:19 pm, edited 1 time in total.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Thu Apr 13, 2006 8:11 pm

try these charmicheal numbers
62745,63973
your code answered normal numbers

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:

Post by sohag144 » Sat Apr 15, 2006 2:17 pm

yeh.i found my bug , i have to use long long in bigmod() function.

johnplayers
New poster
Posts: 5
Joined: Mon Apr 03, 2006 12:52 pm

Post by johnplayers » Wed May 17, 2006 9:26 am

That was very helpful!!
Thnx

User avatar
willima
New poster
Posts: 13
Joined: Wed Dec 07, 2005 1:19 pm
Location: Brazil

Only pre-calculating?

Post by willima » Fri Jul 28, 2006 8:58 pm

I solved this problem by precalculating the Carmichael Numbers and, from the topics above, I think this is the only to solve the problem without TLE. Am I right?
"Don't let the day go by
Don't let it end
Don't let the day go by, in doubts
The anwser lis within"

vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

Re: Plz Help me...

Post by vijay03 » Wed Sep 20, 2006 12:49 pm

J&Jewel wrote: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;
}


The OJ says to print "The number 561 is a Carmichael number.".. while yours prints out "The number 561 is a Charmichael number"..

flehns
New poster
Posts: 4
Joined: Sat Oct 21, 2006 3:30 am

help! I dont understand why I get TLE

Post by flehns » Wed Oct 25, 2006 7:32 am

My computer runs my code so quickly, and gets all of the answers right, but it still gets TLE. I have taken all the advice I could from the boards and even took into account the possibility of entering a value that is not an integer. I am getting pretty frustrated seeing TLE so much.

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

//adapted from prime_factorization()
bool isPrime(unsigned long x)
{
	unsigned long i;			/* counter */
	unsigned long c;			/* remaining product to factor */

	c = x;

	while ((c % 2) == 0) {
		//printf("%ld\n",2);
		c = c / 2;
	}

	i = 3;

	while (i <= (sqrt((double)c)+1)) {
		if ((c % i) == 0) {
			//printf("%ld\n",i);
			c = c / i;
		}
		else
			i = i + 2;
	}

	if (c > 1) return (c == x);
	return 0;
}

//calculates a^n(mod n)
unsigned long fermat(unsigned long a,unsigned long totheN,unsigned long modN) {
	if (totheN==0)
		return 1;
	else if (totheN==1)
		return a%modN; 
	else if (totheN%2==0)
		return (fermat(a,totheN/2,modN)*fermat(a,totheN/2,modN))%modN;
	else
		return ((a%modN)*(fermat(a,totheN-1,modN)%modN))%modN;
}

bool carmnumber(unsigned long n)
{
		for(unsigned int i = 2; i < n; i++)
		{
			if(i == fermat(i,n,n))
			{
				if(isPrime(n)) { return 0; break; }
				return 1;
				break;
			}
			else
			{	return 0;
				break;
			}
		}
}

int main()
{
	double n;
	cin >> n;
	

	while(n != 0)
	{
		if((n-(int)n) > 0) { cout << n << " is normal.\n"; }
		else {
		if(carmnumber((unsigned long)n)) { cout << "The number " << n << " is a Carmichael number.\n"; }
		else { cout << n << " is normal.\n"; }
		}
		cin >> n;
	}
}
When I try to pre-generate, my computer freezes. Please help!

flehns
New poster
Posts: 4
Joined: Sat Oct 21, 2006 3:30 am

Post by flehns » Wed Oct 25, 2006 8:04 am

Can someone give me a hint as to how to precalculate. I tried to precalculate by running through all the numbers from 2 to 65000 and putting it into an array if it was a carmichael number, but this wound up taking sooo much time. :evil:

User avatar
willima
New poster
Posts: 13
Joined: Wed Dec 07, 2005 1:19 pm
Location: Brazil

Precalculating

Post by willima » Tue Oct 31, 2006 10:11 pm

Can someone give me a hint as to how to precalculate. I tried to precalculate by running through all the numbers from 2 to 65000 and putting it into an array if it was a carmichael number, but this wound up taking sooo much time.
Well, precalculating really can take several seconds or even minutes, depending on what platform you use. So, what you can do is run a program that calculate this numbers and another program that returns this number instantly, using a switch case structure.

I coudn't imagine another way to solve the problem.

Good luck!
"Don't let the day go by
Don't let it end
Don't let the day go by, in doubts
The anwser lis within"

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Tue Feb 06, 2007 3:53 pm

going to the link

http://www.comp.nus.edu.sg/~stevenha/pr ... l%20Number

i came to know that the number has exactly 3 or greater prime factor;
but i am confused that why 30 is not a carmaichel number?

30 = (3*5*2);


i know there is a wrong with me. but what is that?
may anyone explaine it?





newton............ simply the best

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Feb 06, 2007 4:20 pm

The link you posted doesn't have enough explanation.

I think this link would be enough to answer your question.
http://mathworld.wolfram.com/CarmichaelNumber.html

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Wed Feb 07, 2007 2:04 pm

Code: Select all


          resolved after AC

thanks, it was a chilly mistake








NEWTON...................... SIMPLY THE BEST!
Last edited by newton on Sat Feb 10, 2007 1:40 pm, edited 2 times in total.

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Wed Feb 07, 2007 10:03 pm

Well, instead of 'Charmichael' you should print 'Carmichael'. =]
Thiago Sonego Goulart - UFMG/Brazil

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Thu Feb 07, 2008 6:48 am

Oh, my god. I just found the silliest bug of my life. I was printing
1729 is a Carmichael number.
instead of
The number 1729 is a Carmichael number.
Almost lost my head trying to find where the WA was...
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

adhoc17
New poster
Posts: 1
Joined: Sat May 31, 2008 9:33 am

Re: 10006 - Carmichael Numbers

Post by adhoc17 » Sat May 31, 2008 9:42 am

i m getting wrong answer in this problem.
it seems to work correctly for all inputs including the 15 carmichael numbers in the range specified.
could anyone plz help me?
my code follows:




#include<iostream>
#include<cmath>
using namespace std;
int isprime(long n)
{ int i;
if(n==1||n==2)
return 0;
for(i=3;i<=(int)sqrt(n)+1;i+=2)
{
if(n%i==0)
return 0;
}
return 1;
}


int expm(long n)
{ unsigned long x,y,m,j;
for( j=2;j<n-1&&!isprime(j);j++)
{
x=1;
y=j;
m=n;
while( m>0)
{
if(m%2==1)
x=((x%n)*(y%n))%n;

y=((y%n)*(y%n))%n;
m/=2;

}
if(x%n!=j)
return 0;
}
return 1;

}



main()
{
unsigned long n;
while(1)
{
cin>>n;
if(n==0)
break;
if(isprime(n)==0&&expm(n)==1)
cout<<"The number "<<n<<" is a Carmichael number."<<endl;
else
cout<<n<<" is normal."<<endl;
}

return 0;
}

help me plz.

Post Reply

Return to “Volume 100 (10000-10099)”