Gegeben eine Zahl N, wie viele Zahlenpaare eine Quadratsumme kleiner oder gleich N haben?

Mal F (N) als die Anzahl von Paaren von verschiedenen positiven ganzen Zahlen (A, B), so dassA 2 + B 2 ≤ N und A < B definieren.Gegeben eine Zahl N, wie viele Zahlenpaare eine Quadratsumme kleiner oder gleich N haben?

Wenn N = 5 das einzig mögliche solches Paar ist (1,2)für N = 10 die Paare sind zwei: (1,2) und(1,3).

Außerdem haben wir F (13) = 3, F (17) = 4, F (17) = 4, F (20) = 5, F (20) = 5, F (25) = 6, F (100) = 31 usw. für jede Zahl, die die Summe zweier unterschiedlicher Quadrate ungleich Null ist.

Bisher habe ich die folgende Lösung:

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; 
}

Gleiche Zahlen sind nicht zählbar, so (1,1) und (2,2) ungültig Tupel sind. Gleiche Kombination aber unterschiedliche Reihenfolge zählt nur einmal. Also (1,2) und (2,1) zählen nur als einmal.

Aber wie der Bereich von N 1 ist, brauche ich einen effizienteren Algorithmus oder eine Formel, um dies zu berechnen. Gibt es einen Trick, um meinen Code effizienter zu machen?

Quelle

2015-12-24 Code Mechanic

Muss * A * kleiner als * B * sein? Ansonsten könnten die Tupel * (2,1) * und * (3,1) * ebenfalls zählen. –

Nein (1,2) und (2,1) beide zählen nur einmal. –

Außerdem, was ist 'lld'? Ich bin ein bisschen vertraut mit C++, weiß aber nicht, um welchen Typ es sich handelt. –

In Pseudo-Code:

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

Quelle

2015-12-24 17:27:51

Funktioniert nicht. Es gibt falsche Ausgabe. F (5) = 1, aber Ihr Programm gibt F (5) = 2. F (100) = 31 aber Ihr Programm gibt F (100) = 38. –

wollen Sie nicht (1,1) und (1,2) für F (5)? Oh, du willst beide Zahlen unterscheiden. kein Problem. bearbeitet –

Nein, Entschuldigung, ich habe vergessen zu erwähnen, die gleichen Nummern sind nicht zählbar. . –

Sie müssen die Anzahl der B ‚s nicht berechnen: Sie können einfach die größte B berechnen, für die dies möglich ist, die sofort die Anzahl der Tupel ist für dass A:

B max = sqrt (NA), und die Untergrenze auf B ist: B _min = A + 1.

Jetzt können Sie wie folgt vorgehen:

Iterierte für A von -sqrt (n);
für jede solche A berechnen Sie die Menge B 's Sie verwenden können;
berechnen Sie die Summe von diesen.

Also das führt uns zu dem folgenden Algorithmus:

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; 
}

von dem Moment an, nicht mehr B Werte gefunden werden kann, man die Suche abbrechen kann.

Ich habe hier eine demo geschrieben, die zu funktionieren scheint.

Quelle

2015-12-24 17:41:36

Gegeben eine Zahl N, wie viele Zahlenpaare eine Quadratsumme kleiner oder gleich N haben?

Antwort

Verwandte Themen