CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • All Contests
    • May Cook-Off
    • May Long 2012
    • April Cook-Off
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Facebook
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
    • Event Calendar
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Tutorials
    • Long Contest Ranks
    • Short Contest Ranks
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » April 2010 Contest » The Big Theorem

The Big Theorem

Problem code: O4

  • All Submissions

You are given integers x and n. You need to find two positive integers a and b, such that a^n - b^n = x^n.

Input :

The first line contains the number of test cases T. Each of the next T lines contains 2 integers x and n.

Output :

Output T lines, one for each test case, containing two integers a and b as needed. If there are multiple solutions, output the one with the smallest a. It is guaranteed that a solution will always exist.

Constraints :

1 <= x <= 100000 3 <= n <= 10


Date: 2010-04-01
Time limit: 1s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


  • Submit

Comments

  • Login or Register to post a comment.

what? how is this possible?

cranil @ 1 Apr 2010 03:08 PM

what? how is this possible?

i m sure all they re trying

suh_ash2008 @ 1 Apr 2010 03:11 PM

i m sure all they re trying to say is: April fool!!!! :):)

lol never realized that

cranil @ 1 Apr 2010 03:12 PM

lol never realized that totally fooled!!! you got me guys! :P :P

no sample I/O?

fushar @ 1 Apr 2010 03:13 PM

no sample I/O?

No X problem this time around

boxer @ 1 Apr 2010 03:21 PM

No X problem this time around ?

@ Abhijit: No!!! i think they

suh_ash2008 @ 1 Apr 2010 03:24 PM

@ Abhijit: No!!! i think they re working on it!!! i read somewhere that this month there are going to be 2 challenge problems!! Check the forums!!!

heyii can you please tell me

akashheart02 @ 1 Apr 2010 03:40 PM

heyii can you please tell me form of output

whether

output:

3 4

or

output:

3

4

@Santosh: Either is ok!!

suh_ash2008 @ 1 Apr 2010 03:56 PM

@Santosh: Either is ok!!

Either output will work fine.

admin @ 1 Apr 2010 04:08 PM

Either output will work fine.

@Subhash The problem

admin @ 1 Apr 2010 04:10 PM

@Subhash The problem statement is fine :)

Can you give a sample

sandeepsingh @ 1 Apr 2010 04:27 PM

Can you give a sample input/output

I think this is a trick

vids @ 1 Apr 2010 04:27 PM

I think this is a trick question, we have to give  a boolean answer stating wether such a thing is possible or not.

So it that just April

cgy4ever @ 1 Apr 2010 04:29 PM

So it that just April fool?

It's in contradiction with Fermat last theorem..

Or it must have some trick!

@ admins   very funny guys.

vprashant1 @ 1 Apr 2010 04:35 PM

@ admins

 

very funny guys. This is the fermat's last theorom. it states that a^n+b^n=x^n if and only if n<=2

so for all numbers greater than 2, u will never be able to find the answer.

 

so similarly, x^n-a^n=b^n is not possible for n<=2...

 

April Fools to all huh?? :P

 

Provide a Example Input And

arjunsab @ 1 Apr 2010 04:40 PM

Provide a Example Input And Output plz..

any test cases, if possible?

mtk @ 1 Apr 2010 04:40 PM

any test cases, if possible?

Actually I have discovered a

u2001137 @ 1 Apr 2010 04:53 PM

Actually I have discovered a truly marvelous code to solve this question but the computational power of your system is too low to run it.

@Neelesh: LOL =))

fushar @ 1 Apr 2010 05:02 PM

@Neelesh: LOL =))

But there is nothing about a

Shmuma @ 1 Apr 2010 05:17 PM

But there is nothing about a and b constraints. The can be negative, I guess. In that case, solution is always exists. But failed to solve this problem, anyway :(.

@Max You need to find two

chirayu @ 1 Apr 2010 05:23 PM

@Max

You need to find two positive integers a and b

 

read question carefully

in input: take 'x' first or

chirayu @ 1 Apr 2010 05:31 PM

in input:

take 'x' first or 'n' first

in output:

print 'a' first or 'b' first

pls hlp?

@admin Please provide some

anurag_aggarwal @ 1 Apr 2010 05:31 PM

@admin Please provide some sample input output cases

wat is the range of test

chirayu @ 1 Apr 2010 05:32 PM

wat is the range of test cases and values of 'a' & 'b'?

@Anurag they cant provide

chirayu @ 1 Apr 2010 05:35 PM

@Anurag

they cant provide input/output sample cases

bcoz by doing dat, trick to this ques will get revealed

i think question is perfectly

akashheart02 @ 1 Apr 2010 05:37 PM

i think question is perfectly right but don't know where is the mistake must be very small.

you are doing programming not math.

@santosh kumar but it is the

chirayu @ 1 Apr 2010 05:44 PM

@santosh kumar

but it is the fermat's last theorem:-

a^n + b^n =c^n is not possible for n>2

the above can be re-written as:

c^n - b^n =a^n

which is the eqn given to us for n>=3

1 <= x <= 100000 3 <= n <=

vids @ 1 Apr 2010 06:02 PM

1 <= x <= 100000 3 <= n <= 10

is this

1 <= x <= 100000 & 3 <= n <= 10

or 1 <= x <= 1000003 <= n <= 10 which is slightly contradictory :P

I know the solution to this

keshav_57 @ 1 Apr 2010 06:52 PM

I know the solution to this problem!!!

Every test case file begins with '0' (The number of test cases!!).

Output nothing. :)

don't we need a limit on T

devvrr @ 1 Apr 2010 06:52 PM

don't we need a limit on T

@admin: This is terribly

keshav_57 @ 1 Apr 2010 06:58 PM

@admin: This is terribly unprofessional behaviour.

heyii if we think ^ as

akashheart02 @ 1 Apr 2010 07:25 PM

heyii if we think ^ as bitwise operator then it is possible but didn't get accepted

anyone has any idea about this

sample i/p: 1 6 2 o/p: 10

suman90.2010 @ 1 Apr 2010 07:47 PM

sample i/p:

1

6 2

o/p:

10 8

but codechef always ignore my solution by saying "time limit exceeded"

@$um@n n >= 3, so 2 is

Shmuma @ 1 Apr 2010 07:51 PM

@$um@n

n >= 3, so 2 is invalid.

@$um@n 3 <= n <= 10

boxer @ 1 Apr 2010 07:54 PM

@$um@n

3 <= n <= 10

I am getting the

anurag_aggarwal @ 1 Apr 2010 07:57 PM

I am getting the answer

I/P

1

1000 3

O/P

6459 6451

is it right pls tell me

LOL it's so funny people are

cranil @ 1 Apr 2010 07:58 PM

LOL it's so funny people are actually trying to code this!!

@max lapan yh,u r right

suman90.2010 @ 1 Apr 2010 07:59 PM

@max lapan

yh,u r right man..i was considering n>=1

@codechef.... Plz tell us if

sankikhopadi @ 1 Apr 2010 08:05 PM

@codechef....

Plz tell us if its solution exists or not..I have been thinking on it for 3 hrs.I searched da whole google n they have even given us the proof of Ferment's Last theorem..I definitely think its wrong..Just tell us if it can be solved or not..Its just waste of time giving this problem.Plz reply sooooooon...

i'm almost done with the

chirayu @ 1 Apr 2010 08:12 PM

i'm almost done with the solution,i just need to know

that

are 'a' and 'b' non zero integers?

am getting the

anurag_aggarwal @ 1 Apr 2010 08:23 PM

am getting the answer

I/P

1

1000 3

O/P

6459 6451

is it right pls tell me

can anyone tell me

@Anurag does not work last

cranil @ 1 Apr 2010 08:36 PM

@Anurag does not work last digit of 6459^3 is 9 and last digit of 6451^3 is 1 so last digit of 6459^3 - 6451^3 is 8... last digit of 1000^3 is 0 :P

@admin: This 'fools' version

screw_it @ 1 Apr 2010 08:50 PM

@admin: This 'fools' version is 'symbolic' of the contests organized here.

@admin: This 'fools' version

keshav_57 @ 1 Apr 2010 08:51 PM

@admin: This 'fools' version is 'symbolic' of the contests organized here.

@admin: This 'fools'

pr0ton @ 1 Apr 2010 08:57 PM

@admin: This 'fools' version is 'symbolic' of the contests organized here.

@everyone If there are

chirayu @ 1 Apr 2010 10:24 PM

@everyone

If there are multiple solutions, output the one with the smallest a.

least value of a is when

a=x;

this gives b=0; which satisfies the eqn also.

so everytime o/p will be:-

x 0

where x is i/p.

@me but i got wrong answer

chirayu @ 1 Apr 2010 10:48 PM

@me

but i got wrong answer through above logic

Lovely Aprill fool prank !

Debanjan @ 1 Apr 2010 11:03 PM

Lovely Aprill fool prank ! You nearly got me :P

if b can be zero?

codegambler @ 2 Apr 2010 12:12 AM

if b can be zero?

@Chirayu the question says

cranil @ 2 Apr 2010 12:16 AM

@Chirayu

the question says positive numbers

@admin..Learn some algebra

kinshuk2jain @ 2 Apr 2010 01:05 AM

@admin..Learn some algebra before posting problems like this. Read Fermat's last theorem which states that a^n+b^n=c^n is not possible for n>2. Or change the question to find real numbers instead of integers.

@kinshuk "learn algebra" real

cranil @ 2 Apr 2010 01:56 AM

@kinshuk "learn algebra" real numbers have too many solutions :P and there is no smallest positive a :P

Just a general comment...

cranil @ 2 Apr 2010 01:59 AM

Just a general comment... Fermat's last Theorem is one conjuncture which was called a "theorem" even before it was proved... and the Poincaré conjuncture is still called a "conjuncture" (it's proved)...

watz wrong wit u

justfor @ 2 Apr 2010 01:12 PM

watz wrong wit u guys...?

did anyone hack dis site n driving the users AWAY from this site or wat...?!!!

i had a lot of respect towards this site but now u r loosing that...

hope u will rectify everything...

n y r the previous winners

justfor @ 2 Apr 2010 01:13 PM

n y r the previous winners of old contests not working on this contest....?

hey buddies have a look on this point...

@admin: when will the actual

suh_ash2008 @ 2 Apr 2010 01:28 PM

@admin: when will the actual contest start?? We are all waiting!!!

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of computer programming. At CodeChef we work hard to revive the geek in you by hosting programming contests on a monthly basis. We also aim to have training sessions and events related to online programming for programmers around the world. Apart from providing a platform for programming competitions, CodeChef also has various tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our judge accepts solutions in over 35+ programming languages. Online programming was never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming competitions that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly programming contests and the shorter format Cook-off programming contests. Put yourself up for recognition and win great prizes. Prizes worth up to Rs.20,000 and $700 are up for grabs every month along with lots more CodeChef goodies.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be part of CodeChefs Forums and interact with all our programmers love helping out other programmers and share their ideas.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. Be a part of the CodeChef community through CodeChef meetups and techtalks. You can also host a programming contest for your institute on CodeChef and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com