GCDEX - GCD Extreme
Given the value of N, you will have to find the value of G. The meaning of G is given in the following code
G = 0; for (i = 1; i < N; i++) for (j = i+1; j <= N; j++) G += gcd(i, j);Here gcd() is a function that finds the greatest common divisor of the two input numbers.
Input
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1 < N < 1000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.
Output
For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.
Example
Input: 10 100 200000 0 Output: 67 13015 143295493160 Time limit has been changed. Some AC solutions get TLE
hide comments
|
sunny_saraff:
2020-07-09 12:24:14
Time limit is too strict although AC in 2 GO!!
|
|
fairooj_04:
2020-04-25 11:47:19
I used euler Totient function.....and getting runtime (SIGSEV) , can anyone help me here? |
|
mushfiq4513:
2019-05-12 16:21:48
modified sieve and totient function..... AC :) |
|
DK...:
2019-03-16 15:13:43
Try to compute everything into arrays, using vector's push_back function makes TL |
|
whyamievenhere:
2018-12-19 20:02:17
TLE is killing me here... time limit is really ridiculous, |
|
badboy_1496:
2018-07-17 06:08:56
hurray!!!! ac in one go...nice way of using sieves
|
|
excel_blaze:
2018-05-21 16:07:54
simple logic and implementation(^_^)
|
|
nadstratosfer:
2018-03-21 19:09:52
Took me 7+ hours in 3 sittings to fit within this retarded TL in PyPy. Props to julkas for showing it's possible.
|
|
anupamwadhwa:
2018-02-07 19:30:21
Try NTG after this one. |
|
include_sajal:
2018-01-13 18:13:41
Using Euler Phi will bring extra overheads. Try something different. Though one can apply Euler Phi cautiously to get AC. BTW, an awesome one! |
Added by: | Phenomenal |
Date: | 2009-02-16 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | ACM World Final Warm up 1 - 2008 |