Re: задачка: A^3+B^3+C^3=D^3

From

Oleg I. Khovayko ()

To

Vjacheslav Maslov ()

Date

2003-03-07T20:29:52Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>


Vjacheslav Maslov wrote:
> 
> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает, что
> придумал алгоритм решения этой задачи, который отрабатывает за 2 сек на машине
> класса P III.

Ну вот ниже решение. Отрабатывает, правда, не ровно за 2 секунды, но сопоставимо:

real    0m2.402s
user    0m2.190s
sys     0m0.210s

Если раскомментировать вывод - еще секунда добавится...


#include <map>
#include <set>
#include <iostream>

using namespace std;

int calc(int max) {
  map< int, set< int > > cd;
  int rescount = 0;  
  for(short d = 2; d <= max; d++)
    for(short c = 1; c < d; c++)
     cd[d*d*d-c*c*c].insert((c << 16) | d);
     
  for(short a = 1; a <= max; a++)
    for(short b = a; b <= max; b++) {
      int ab = a*a*a + b*b*b;
      if(cd.count(ab)) {
        const set< int > &cds = cd[ab];
        for(set< int >::const_iterator it(cds.begin());
        it != cds.end(); ++it) {
	      rescount++;
               // cout << "Result: " << a << " " << b << " " 
	       // << (*it >> 16) << " = " << ((short)*it) << endl; 
	     } 
	   }
     } 
   return rescount; 
}

main() {
  int cnt = calc(1000);
  cout << "Found results:" << cnt << endl; 
}


-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)