Dato un numero N quante coppie di numeri hanno una somma quadrata inferiore o uguale a N?

Question

DefiniamoF (N) il numero di coppie di numeri interi positivi distinti (A, B) tale che A + B ≤n e A < B.

Se N = 5 l'unico tale coppia è possibile (1,2) per N = 10 le coppie sono due: (1,2) e(1,3).

Inoltre abbiamo F (13) = 3, F (17) = 4, F (17) = 4, F (20) = 5, F (20) = 5, F (25) = 6, F (100) = 31 e così via per ogni numero che è la somma di due quadrati diversi da zero.

Finora ho la seguente soluzione:

long long SOLVE(lld n) 
{ 
    long long x=sqrt(n),up=0; 
    long long a=x,b=1; 
    while(abs(a-(b-1))!=1) 
    { 

     while(sqr(a)+sqr(b)<=n) 
     { 
      b++; 
     } 
     up+=(b-1); 
     a--; 
    } 
    b--; 
    up+=(b*(b+1))/2; 
    return up; 
} 
int main() 
{ 
     cout<<number(100); 
return 0; 
} 

numeri stessi non sono numerabili, quindi (1,1) e(2,2) sono tuple non validi. La stessa combinazione ma conteggio di ordini diversi una sola volta. Pertanto, (1,2) e (2,1) contano solo come una volta.

Tuttavia, poiché l'intervallo di N è 1, ho bisogno di un algoritmo o di una formula più efficienti per calcolarlo. C'è qualche trucco per rendere il mio codice più efficiente?

Answer 1

In pseudocodice:

int count=0; 
for (smaller=1; ;++smaller) 
{ 
    maxlarger = floor(sqrt(N-smaller*smaller)); 
    if (maxlarger <= smaller) 
     break; 
    count+=(maxlarger-smaller); 
} 
return count; 

Answer 2

Non è necessario per calcolare il numero di B s': si può semplicemente calcolare il più grande B per cui ciò è possibile, che è immediatamente il numero di tuple per che a:

B _max = sqrt (NA), e il basso legato sulla B è: B _min = A + 1.

Ora è possibile effettuare le seguenti operazioni:

• iterare per Un da -sqrt (n);
• per ciascuno di tali A calcolare la quantità di B che è possibile utilizzare;
• calcolare la somma di questi.

Quindi questo ci porta alla seguente algoritmo:

lld SOLVE(lld n) { 
    lld aM=sqrt(n); 
    lld a=1; 
    lld res = 0; 
    for(lld a = 1; a < aM; a++) { 
     int nB = sqrt(n-a*a)-a; 
     if(nB > 0) { 
      res += nB; 
     } else { 
      break; 
     } 
    } 
    return res; 
} 

dal momento in cui, non più B valori possono essere trovati, si può interrompere la ricerca.

Ho scritto un demo qui che sembra funzionare.