How to calculate solutions to x+y+z = u+v+w, 0 <= x, y, z, u, v, w < n.

Правка en2, от PoIycarp, 2024-03-31 23:07:10

So I'm trying to solve this problem but my solution has O(n^6) complexity and I don't know how you can do this faster.

int ans = 0;
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int k = 0; k < n; k++){
            for(int x = 0; x < n; x++){
                for(int y = 0; y < n; y++){
                     for(int z = 0; z < n; z++){
                         if(i + j + k == x + y + z) ans++;
                     }
                 }
            }
        }
    }
}
cout << ans << "\n";

I looked up the sequence on OEIS but there isn't any other relevant information.
https://oeis.org/search?q=1+%2C+20+%2C+141+%2C+580+%2C+1751&language=english&go=Search
I need to calculate this fast for n <= 100000.

Теги help, complexity, oeis

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский PoIycarp 2024-03-31 23:07:10 18
en1 Английский PoIycarp 2024-03-31 23:06:28 889 Initial revision (published)