Number Strength

1

1 votes
Medium, Math
Problem

Charlie being a maths genius  loves playing with numbers.One of his friend named John gave him a challenge.In the challenge Charlie would be Given a number n and he has to find the STRENGTH of n. 

The STRENGTH of n is calculated by following steps:

  • Find the divisors of n (including 1and n)
  • For each divisor d calculate the number of integers r in range [1,d], such that gcd(r,d)=1
  • add all the values obtained for the divisors of n to get the STRENGTH of n

Charlie being busy in school assignment asks You for help.

INPUT :

  • First line contains an integer t indicating number of test cases
  • Next t lines each contain an integer n.

OUTPUT :

  • Print out t lines each having STRENGTH of corresponding n

CONSTRAINT :

  • 1<=t<=105
  • 2<=n<=1018

Problem Setter: Harkanwar Singh

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

First line indicates the number of test cases that is 1.

Then in next line we get n=6.

The divisor of n are {1,2,3,6}

For 1 numbers less than equal to 1 that have gcd =1 with 1 are {1} hence 1 number

For 2 numbers less than equal to 1 that have gcd =1 with 1 are {1}  hence 1 number    

For 3 numbers less than equal to 1 that have gcd =1 with 1 are {1,2} hence 2 numbers

For 6 numbers less than equal to 1 that have gcd =1 with 1 are {1,5} hence 2 numbers

So for each all divisor we get STRENGTH of 6=1+1+2+2=6

Editor Image

?