Число четких прямоугольников, в которых диагональ проходит по N квадратам

Question

Я решаю проблему CS, и мне мало нужна помощь. У меня число N, и мне нужно подсчитать количество различных прямоугольников, в которых диагональ проходит по N квадратам, если прямоугольник разбит на прямоугольники размером 1x1. Эта фотография поможет вам понять.

Эта картина показывает все 4 комбинации, если N = 4, на самом деле прямоугольники, в которых диагонали проходит в 4-х квадратов с размерами 1x4, 2x3, 4x2 и 4x4.

Я нашел формулу, если мы дали два размера прямоугольников оно:

А + В - НОД (А, В)

, так как N < = 10^6, я идти вверх до 10^6 и проверить для каждого N делители N, сложность которого равна O (N sqrt (N)), так как дивизоры A являются gcd (A, B) i решают систему уравнений q является делителем из A и q является gcd (A, B) A + Bq = N и gcd (A, B) = q Я решил это в O (N sqrt (N) * log (N)) , где я предполагаю, что log (N) - это время, чтобы найти gcd двух номера.

Поскольку срок составляет 3 секунды, он не работает вовремя. Мне нужна помощь в оптимизации решения.

Update: Вот мой код:

#include <bits/stdc++.h> 

#define ll long long 
using namespace std; 
int a; 

int gcd(int a, int b) { 
    if(b>a) swap(a,b); 
    if(b==0) return a; 
    return gcd(b, a%b); 
} 

bool valid(int n, int m, int gc, int a) { 
    if(n+m-gc==a) return true; 
    return false; 
} 

int main() { 
cin>>a; 

int counter=0; 
for(int i=1;i<=a/2;i++) { 
    for(ll j=1;j<=sqrt(i);j++) { 
     if(i%j==0) { 
      if(j!=i/j) { 
       int m1 = a+j-i; 
       int div=i/j; 
       int m2 = a+div-i; 
       if(valid(i, m1, j, a)) { 
        if(gcd(i, m1)==j) 
         counter++; 
       } 
       if(valid(i, m2, i/j, a)) { 
        if(gcd(i,m2)==i/j) 
         counter++; 
       } 

      } 
      else { 
       int m1 = a+j-i; 
       if(valid(i, m1, j, a)) { 
        if(gcd(i, m1)==j) 
         counter++; 
       } 
      } 
     } 
    } 
} 
cout<<counter+1; 
return 0; 
} 

Спасибо заранее.

Answer 1

Хотя O(n*sqrt(n)*log(n)) звучит немного много для n <= 10^6, и вы, вероятно, потребуется немного лучший алгоритм, ваш код поддерживает несколько оптимизаций:

int gcd(int a, int b) { 
    if(b>a) swap(a,b); 
    if(b==0) return a; 
    return gcd(b, a%b); 
} 

Избавьтесь от свопа, она будет прекрасно работать и без него.

Пока вы на него, чтобы избавиться от рекурсии тоже:

int gcd(int a, int b) { 
    while (b) { 
     int r = a % b; 
     a = b; 
     b = r; 
    } 

    return a; 
} 

Следующая:

for(int i=1;i<=a/2;i++) { 
    for(ll j=1;j<=sqrt(i);j++) { 

Compute a/2 и sqrt(i) вне их соответствующих петель. Нет необходимости вычислять его на каждой итерации. Компилятор может или не может быть достаточно умным (или настроенным), чтобы сделать это сам, но вы не должны полагаться на него, особенно в настройках онлайн-судьи.

Вы также можете прекомпотировать i/j дальше вниз, чтобы не перепрограммировать его каждый раз. Много делений может быть медленным.

Далее, вам действительно нужно long long для j? i - это int, а j подходит к его квадратному корню. Поэтому вам не нужно long long для j, используйте int.