НОД Экстрим 2 - Задачи

This condition same as GCD extremeI..:)) but its condition must be different :))

There is " 1 < n < 200001 " in problem condition, I think it is wrong it must be 1 < n < 4000001.. (I accepted this problem )

awpris ответил:

And you look at the restrictions, including time ... :)

kazim_255

import java.util.Scanner;

public class Main { static final int MAX = 4000001; static long n; static long[] d = new long[MAX]; static long[] fi = new long[MAX];

static void fillEuler() {
    for (int i = 2; i < MAX; i++) fi[i] = i;

    for (int i = 2; i < MAX; i += 2) fi[i] /= 2;

    for (int i = 3; i < MAX; i += 2)
        if (fi[i] == i)
            for (int j = i; j < MAX; j += i) fi[j] -= fi[j] / i;
}

static void f() {
    int SQRT_MAX = (int) Math.sqrt(MAX);
    for (int i = 2; i <= SQRT_MAX; i++) {
        d[i * i] += i * fi[i];
        for (int j = i * i + i, k = i + 1; j < MAX; j += i, k++)
            d[j] += i * fi[k] + k * fi[i];
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    fillEuler();
    System.arraycopy(fi, 0, d, 0, MAX);
    f();
    for (int i = 3; i < MAX; i++) d[i] += d[i - 1];
    while ((n = scanner.nextLong()) != 0) System.out.println(d[(int) n]);
}

}