You are not logged in. Please login at www.codechef.com to post your questions!

×

ENIGMA02 - Editorial

PROBLEM LINK:

Playing with Numbers

Author and Editorialist : Shefali Chaudhary

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Euler Phi Function.

PROBLEM:

Given n, calculate the sum LCM(1,n)+LCM(2,n)+...+LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

EXPLANATION:

Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n . Thus, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd (n, k) = 1.

Solution is somewhat mathematical to this problem. summation of LCM(i,n) for all i belongs to [1,n] is equal to ((summation of ETF(d) + 1)*n)/2 where ETF(d) is euler totient function of d and d belongs to the set of divisors of n.

You simply have to precompute the euler function for all values upto the max given constraint of 1000000. So that we can find the phi function of any given value and thus compute the result for ((summation of ETF(d) + 1)*n)/2 .

For better understanding have a look at the code of calculating the phi function in the link below: http://www.geeksforgeeks.org/eulers-totient-function/

SOLUTIONS:

Solution Link

This question is marked "community wiki".

asked 16 Oct '15, 20:07

sumit.asr_128's gravatar image

2★sumit.asr_128
464
accept rate: 10%

edited 16 Oct '15, 22:54

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,684
×1,672
×43
×42

question asked: 16 Oct '15, 20:07

question was seen: 2,103 times

last updated: 16 Oct '15, 22:54