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.
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.
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.
Input: 10 100 200000 0 Output: 67 13015 143295493160 Time limit has been changed. Some AC solutions get TLE
Can be done without using phi values!And in much quicker time,because of the same! :)
~ adieus ~:
O(n^(3/2)) wont work ??
.:: Pratik ::.:
got ACC on UVA in 0.032s but TLE here :(Last edit: 2009-06-14 15:22:30
correct task: http://icpcres.ecs.baylor.edu/onlinejudge/external/114/11424.html
The problem setter has been banned for his cheating actions. To see the original description, you may go to UVa Online Judge(http://icpcres.ecs.baylor.edu) and find that problem(id:11426).