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
Rishav Goyal:
2014-06-19 13:52:49
w**********k is wrong with spoj!!
|
|
Yu Zhijingcheng:
2014-03-20 16:29:59
Look here if you got TLE
|
|
王泽宇:
2014-03-13 08:41:28
Practice mathematics! |
|
Guilherme Sena:
2014-03-07 22:14:20
ATTENTION: MAXIMAL N = 1000000!!! |
|
Piyush Raman Srivastava:
2014-01-24 20:42:15
so much to understand for this problem!! :-/
|
|
hahaha:
2013-11-27 08:31:03
Time limit is too strict got AC in UVA
|
|
$iddharth prasad:
2013-09-21 09:15:45
getting tle how to optimize ?? |
|
YangYue:
2012-12-07 08:19:57
O(n) can solve it |
|
Renato Ferreira:
2012-07-10 17:39:21
Optimization tips: do not overuse long long and read the whole input using fread, then parse the integers. |
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 |