We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #122: Efficient exponentiation

Project Euler #122: Efficient exponentiation

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 122 from projecteuler.net

The most naive way of computing requires fourteen multiplications:

But using a "binary" method you can compute it in six multiplications:






However it is yet possible to compute it in only five multiplications:





We shall define to be the minimum number of multiplications to compute . For example .

For a given , compute , and also output the sequence of multiplications needed to compute . See the sample output for more details.

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints


Input file #1: .
Input file #2: .

Output Format

For each test case, first output in a single line. Then output lines, each of the form n^a * n^b = n^c, where a, b and c are natural numbers. You may also output n instead of n^1. Use the * (asterisk/star) symbol, not the letter x or something else.

The sequence of multiplications must be valid. Any valid sequence will be accepted.

Sample Input

2
2
15

Sample Output

1
n^1 * n^1 = n^2
5
n * n = n^2
n^2 * n = n^3
n^3 * n^3 = n^6
n^6 * n^6 = n^12
n^12 * n^3 = n^15

Explanation

The second case, , is the example given in the problem statement.

The sample output illustrates that you can use n instead of n^1.

Author

kevinsogo

Difficulty

Easy

Max Score

100

Submitted By

528

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy