In the problem you need to find G by the entered value n . GCD (i, j) is the gcd of numbers i and j .

enter image description here

The program works as it should, but for large n the execution time is colossal (for n = 30,000, for example, the program runs for about a minute).

Can you tell me how to optimize it?

Some questions:

1) Judging by the amounts, the numbers i and j are Fibonacci numbers, am I right? And if so, can this somehow help to facilitate the NOD search algorithm (the greatest common divisor of two Fibonacci numbers is equal to the Fibonacci number with the index equal to the largest common divider of the indices)? To search for ged, I used the Euclidean algorithm.

2) Is it possible to somehow speed up the calculation of the sum, that is, to avoid the use of two nested cycles and a huge number of iterations arising from them?

public class Main { public static void main(String[] args){ Scanner reader = new Scanner(System.in); int n; List<Integer> a = new ArrayList<>(); for( ; ; ) { n = reader.nextInt(); if(n>1 && n<4000001) a.add(n); else if(n==0) break; } int i, j; for (int k=0; k<a.size(); k++) { n=a.get(k); long G = 0; for( i = 1; i < n; i++) { for( j = i + 1;j <= n; j++) { G += GCD(i,j); } } System.out.println(G); } } static int GCD (int i, int j) { while (j !=0) { int tmp = i%j; i = j; j = tmp; } return i; } }
  • and how much you need to accelerate? if by small things then gcd () is predicted for all pairs (this removes the log from complexity), notice that gcd (i, j + i) = gcd (i, j) and use that the nested loop is not completely, but the complexity will be of order N ^ 2 anyway. Or globally improved to N log N, but the solution will be more difficult. Or you can even calculate locally all the answers up to 100'000 for example, and the solution will be stupid to print the number. - pavel
  • Judging by the fact that in the example the case for n = 200000 execution takes less than ten seconds, you need to speed up very much - koee
  • This is not a question of programming, but of mathematics. Learn from mathematicians how to turn your expression into something shorter. - VladD

1 answer 1

I am writing a general idea. Note that GCD(i,j+i) = GCD(i,j) . Thus, we can perform 2 цикл от 0 до i and multiply the resulting result by the number of occurrences ( N/i - (N%i < j) ). This will reduce the complexity to N ^ 2/2, which is still a lot.

Now 1 more optimization. We will start up 2 cycles not by j but by the result. To do this, we will factor the numbers from 1 to N , for example, the modification of the sieve of Eratosthenes, the main thing is not N or N log N.

i fixed. Based on the factorization, we generate all dividers and sort them in ascending order.

The cycle of divisors ( q ). The number of occurrences of q from 1 to N will be equal to N/q - i/q (minus due to the fact that the cycle from i+1 and not 1). It is this value ( N/q*q ) that we add to the answer. BUT if q not simple, then we took it into account when calculating the answer for its divider. Now we must subtract this value. For each prime divider q ( z ) (it’s better to also calculate separately, there will be less confusion) we must subtract N/q*(q/z) (1 time for each z ). But we will subtract some of them 2 times (for 2 different z ). The next inclusion lemma is the exception.

Consider the example of calculating the sum when for (int i=1;i<=24;i++) ans+=GCD(24,i) Such an example to simplify understanding. Factorization 24 =2*2*2*3 Divisors 1 2 3 4 6 8 12 24 . Sums of the answer step by step:

 24*1 = 24 - 0 +24 24/2*2 = 24; - 12*1 = 12; +12 24/3*3 = 24; - 8*1 = 8; +16 24/4*4 = 24; - 6*2 = 12; +12 24/6*6 = 24; - 4*(2+3-1)=16 +8 24/8*8 = 24; - 3*4 = 12 +12 = 24; - 2*(6+4-2)=16 +8 = 24; - 1*(12+8-4) +8

Total +100.

You can count that the answer is correct.

The complexity will be hard to estimate, but there will be something on the order of N * sqrt (N).

PS in a real task (not an olympiad), I would not do all this, but would calculate the array of constants up to how much you need (400'000 as I remember) and put it in a separate file, yes it would weigh 2-3 megabytes, yes it was created half an hour, but everyone understood how it is generated and the probability of an error would be low.

  • "GCD (i, j + i) = GCD (i, j)" is incorrect. GCD (2, 4) = 2! = 1 = GCD (2, 3) - dzhioev
  • @jzhioev sorry, but 4 = 3 + 2? - pavel
  • I apologize, read "j + 1" vsto "j + i" - dzhioev