{"id":283083,"date":"2016-12-27T08:20:04","date_gmt":"2016-12-27T05:20:04","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=283083"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=283083","title":{"rendered":"10 \u043d\u043e\u0432\u044b\u0445 \u0441\u043a\u0430\u0437\u043e\u043a \u043e \u043f\u043e\u0442\u0435\u0440\u044f\u043d\u043d\u043e\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0438"},"content":{"rendered":"

\u041f\u0440\u0438\u0432\u0435\u0442 \u0425\u0430\u0431\u0440!<\/p>\n

\u042f \u0440\u0435\u0448\u0438\u043b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u0441\u0435\u0440\u0438\u044e<\/a> \u0441\u0442\u0430\u0442\u0435\u0439<\/a> \u043f\u0440\u043e \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0443 \u042d\u0439\u043b\u0435\u0440\u0430, \u043d\u0430\u043f\u0438\u0441\u0430\u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0438\u043e\u0444\u0430\u043d\u0442\u043e\u0432\u0430 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0432\u0438\u0434\u0430 a5<\/sup> + b5<\/sup> + c5<\/sup> + d5<\/sup> = e5<\/sup>.<\/p>\n

<\/div>\n

\u041a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u043a\u0430\u043a\u0443\u044e-\u043b\u0438\u0431\u043e \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043f\u0443\u043d\u043a\u0442\u044b: <\/p>\n

    \n
  1. \u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/li>\n
  2. \u0411\u044b\u0441\u0442\u0440\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/li>\n
  3. \u041c\u043e\u0449\u043d\u043e\u0435 \u0436\u0435\u043b\u0435\u0437\u043e<\/li>\n
  4. \u0420\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0432\u0430\u043d\u0438\u0435<\/li>\n<\/ol>\n

    \u042f \u0443\u0434\u0435\u043b\u0438\u043b \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u043f\u0443\u043d\u043a\u0442\u0443. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u0447\u0442\u043e \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c.
    <\/a>
    \u0421\u0440\u0430\u0437\u0443 \u043e\u0442\u043c\u0435\u0447\u0443, \u0447\u0442\u043e \u043a\u043e\u0434 \u043f\u0438\u0441\u0430\u043b\u0441\u044f \u043d\u0430 \u0421++, \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f 32-\u0431\u0438\u0442\u043d\u044b\u0439 MS Visual C++ 2008 Compiler \u0438 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u043b\u0441\u044f \u0432 \u043e\u0434\u0438\u043d \u043f\u043e\u0442\u043e\u043a \u043d\u0430 \u043c\u0430\u0448\u0438\u043d\u0435 i5-2410M 2.3Ghz. \u041f\u0440\u043e\u0441\u0442\u043e \u043c\u043d\u0435 \u0442\u0430\u043a \u0443\u0434\u043e\u0431\u043d\u0435\u0435 \u2014 \u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043e\u0434 \u043b\u0435\u0436\u0430 \u043d\u0430 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043c\u043e\u0449\u043d\u043e\u043c \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0435, \u0430 64-\u0431\u0438\u0442\u043d\u044b\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043b\u0435\u043d\u044c. \u0417\u0430\u043c\u0435\u0440\u044b \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043d\u0435 \u0431\u043b\u0435\u0449\u0443\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u043e\u0434 \u0440\u0435\u0434\u043a\u043e \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u043b\u0441\u044f \u0431\u043e\u043b\u0435\u0435 1 \u0440\u0430\u0437\u0430 \u043d\u0430 \u0437\u0430\u043c\u0435\u0440, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0434\u0440\u0443\u0433\u0438\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u044b \u0432\u0440\u043e\u0434\u0435 \u0431\u0440\u0430\u0443\u0437\u0435\u0440\u0430 \u043c\u043e\u0433\u043b\u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0432\u043b\u0438\u044f\u0442\u044c \u043d\u0430 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b. \u041e\u0434\u043d\u0430\u043a\u043e \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0446\u0435\u043b\u0435\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u0430\u044f.<\/p>\n

    \u0421\u043a\u0430\u0437\u043a\u0430 #1 \u0437\u0430 O(n5<\/sup>)<\/h1>\n

    \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u0442\u0443\u043f\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c. \u041a\u043e\u0434: <\/p>\n

    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    long long gcd( long long x, long long y ) {     while (x&&y) x>y ? x%=y : y%=x;     return x+y; }  void tale1( int n ) {     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)             for (int c=b+1; c<=n; c++)                 for (int d=c+1; d<=n; d++)                     for (int e=d+1; e<=n; e++)                     {                         long long a5 = (long long)a*a*a*a*a;                         long long b5 = (long long)b*b*b*b*b;                         long long c5 = (long long)c*c*c*c*c;                         long long d5 = (long long)d*d*d*d*d;                         long long e5 = (long long)e*e*e*e*e;                         if (a5 + b5 + c5 + d5 == e5)                             if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                                 printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                     } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u044d\u0442\u043e \u043d\u0435 \u0441\u0430\u043c\u043e\u0435 \u0442\u0443\u043f\u043e\u0435, \u0438\u0431\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0433\u043e\u043d\u044f\u0442\u044c \u043e\u0442 1 \u0434\u043e n \u0438 \u0432 \u043a\u043e\u043d\u0446\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c, \u0447\u0442\u043e a<b<c<d<e. \u041d\u043e \u0442\u043e\u0433\u0434\u0430 \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0431\u044b \u043d\u0443 \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0434\u043e\u043b\u0433\u043e \u0436\u0434\u0430\u0442\u044c. \u0412\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b:  <\/p>\n\n\n\n\n\n
    n<\/th>\n\u0412\u0440\u0435\u043c\u044f<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n<\/tr>\n<\/table>\n
      \u041f\u043b\u044e\u0441\u044b: \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u043a\u0430\u043a \u0432\u0430\u043b\u0435\u043d\u043e\u043a, \u0431\u044b\u0441\u0442\u0440\u043e \u043f\u0438\u0448\u0435\u0442\u0441\u044f, \u0442\u0440\u0435\u0431\u0443\u0435\u0442 O(1) \u043f\u0430\u043c\u044f\u0442\u0438, \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 275<\/sup> + 845<\/sup> + 1105<\/sup> + 1335<\/sup> = 1445<\/sup>.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u043e\u043d\u043e \u0442\u043e\u0440\u043c\u043e\u0437\u043d\u0443\u0442\u043e\u0435<\/i>.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #2 \u0437\u0430 O(n4<\/sup>log n)<\/h1>\n
      \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u043c \u043d\u0430\u0448\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u041f\u043e \u0441\u0443\u0442\u0438, \u044d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u0435\u043d \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u043b \u0442\u043e\u0432\u0430\u0440\u0438\u0449 drBasic<\/a>.  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale2( int n ) {     vector< pair< long long, int > > vec;     for (int a=1; a<=n; a++)         vec.push_back( make_pair( (long long)a*a*a*a*a, a ) );     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)             for (int c=b+1; c<=n; c++)                 for (int d=c+1; d<=n; d++)                 {                     long long a5 = (long long)a*a*a*a*a;                     long long b5 = (long long)b*b*b*b*b;                     long long c5 = (long long)c*c*c*c*c;                     long long d5 = (long long)d*d*d*d*d;                     long long sum = a5+b5+c5+d5;                     vector< pair< long long, int > >::iterator                         it = lower_bound( vec.begin(), vec.end(), make_pair( sum, 0 ) );                     if (it != vec.end() && it->first==sum)                         if (gcd( a, gcd( gcd( b, c ), gcd( d, it->second ) ) ) == 1)                             printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, it->second );                 } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u0422\u0443\u0442 \u043c\u044b \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432, \u043a\u0443\u0434\u0430 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u043f\u044f\u0442\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 1 \u0434\u043e n, \u043f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u0432\u043d\u0443\u0442\u0440\u0438 \u0447\u0435\u0442\u044b\u0440\u0435\u0445 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0446\u0438\u043a\u043b\u043e\u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0435\u0441\u0442\u044c \u043b\u0438 \u0447\u0438\u0441\u043b\u043e a5<\/sup> + b5<\/sup> + c5<\/sup> + d5<\/sup> \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438\u043b\u0438 \u043d\u0435\u0442.  <\/p>\n\n\n\n\n\n\n
    n<\/th>\n\u0412\u0440\u0435\u043c\u044f #1<\/th>\n\u0412\u0440\u0435\u043c\u044f #2<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/tr>\n<\/table>\n
      \u042d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0443\u0436\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0443 \u043c\u0435\u043d\u044f \u0434\u0430\u0436\u0435 \u0445\u0432\u0430\u0442\u0438\u043b\u043e \u0442\u0435\u0440\u043f\u0435\u043d\u0438\u044f \u0434\u043e\u0436\u0434\u0430\u0442\u044c\u0441\u044f \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0434\u043b\u044f n=1000.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u0432\u0441\u0435 \u0435\u0449\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0442\u0443\u043f\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e \u043f\u0438\u0448\u0435\u0442\u0441\u044f, \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0442\u0440\u0435\u0431\u0443\u0435\u0442 O(n) \u043f\u0430\u043c\u044f\u0442\u0438, \u0432\u0441\u0435 \u0435\u0449\u0435 \u0442\u043e\u0440\u043c\u043e\u0437\u043d\u0443\u0442\u043e\u0435<\/i>.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #3 \u0437\u0430 O(n4<\/sup>log n), \u043d\u043e \u0441 O(1) \u043f\u0430\u043c\u044f\u0442\u0438<\/h1>\n
      \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043d\u0435\u0442 \u0441\u043c\u044b\u0441\u043b\u0430 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438 \u0438\u0441\u043a\u0430\u0442\u044c \u0442\u0430\u043c \u0447\u0442\u043e-\u0442\u043e \u0431\u0438\u043d\u043f\u043e\u0438\u0441\u043a\u043e\u043c. \u041c\u044b \u0436\u0435 \u0438 \u0442\u0430\u043a \u0437\u043d\u0430\u0435\u043c \u043a\u0430\u043a\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u044d\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i. \u041c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0431\u0438\u043d\u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u00ab\u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u043c\u00bb \u043c\u0430\u0441\u0441\u0438\u0432\u0435. \u0421\u043a\u0430\u0437\u0430\u043d\u043e \u2014 \u0441\u0434\u0435\u043b\u0430\u043d\u043e:  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale3( int n ) {     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)             for (int c=b+1; c<=n; c++)                 for (int d=c+1; d<=n; d++)                 {                     long long a5 = (long long)a*a*a*a*a;                     long long b5 = (long long)b*b*b*b*b;                     long long c5 = (long long)c*c*c*c*c;                     long long d5 = (long long)d*d*d*d*d;                     long long sum = a5+b5+c5+d5;                     if (sum <= (long long)n*n*n*n*n)                     {                         int mi = d, ma = n; \/\/ invariant: for mi <, for ma >=                         while ( mi+1 < ma )                         {                             int s = ((mi+ma)>>1);                             long long tmp = (long long)s*s*s*s*s;                             if (tmp < sum) mi = s;                             else ma = s;                         }                         if (sum == (long long)ma*ma*ma*ma*ma)                             if (gcd( a, gcd( gcd( b, c ), gcd( d, ma ) ) ) == 1)                                 printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, ma );                     }                 } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0435 \u043d\u0443\u0436\u0435\u043d, \u0443 \u043d\u0430\u0441 \u0447\u0438\u0441\u0442\u044b\u0439 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a.  <\/p>\n\n\n\n\n\n\n
    n<\/th>\n\u0412\u0440\u0435\u043c\u044f #1<\/th>\n\u0412\u0440\u0435\u043c\u044f #2<\/th>\n\u0412\u0440\u0435\u043c\u044f #3<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n<\/tr>\n<\/table>\n
      \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0435\u043b\u043e, \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e, \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0438\u043d\u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u044b \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0437\u0430\u043d\u043e\u0432\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043f\u044f\u0442\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u041d\u0443 \u0438 \u043b\u0430\u0434\u043d\u043e.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u0442\u0440\u0435\u0431\u0443\u0435\u0442 O(1) \u043f\u0430\u043c\u044f\u0442\u0438, \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0442\u043e\u0440\u043c\u043e\u0437\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #4 \u0437\u0430 O(n4<\/sup>)<\/h1>\n
      \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0435\u0449\u0435 \u0440\u0430\u0437 \u0432\u0441\u043c\u043e\u0442\u0440\u0438\u043c\u0441\u044f \u0432 \u043d\u0430\u0448\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435:<\/p>\n
      a5<\/sup> + b5<\/sup> + c5<\/sup> + d5<\/sup> = e5<\/sup><\/p>\n
      \u0438\u043b\u0438, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b A = B.<\/p>\n
      \u041f\u0443\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043d\u0430\u0448\u0438 4 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0446\u0438\u043a\u043b\u0430. \u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f a, b \u0438 \u0441 \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043a\u0430\u043a \u0441\u0435\u0431\u044f \u0432\u0435\u0434\u0443\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f d \u0438 e. \u041f\u0443\u0441\u0442\u044c \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e d=x \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 e, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e A<=B, \u0440\u0430\u0432\u043d\u043e y. \u0414\u043b\u044f d=x \u043d\u0430\u043c \u043d\u0435\u0442 \u0441\u043c\u044b\u0441\u043b\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f e>y. \u0417\u0430\u043c\u0435\u0442\u0438\u043c \u0442\u0430\u043a\u0436\u0435, \u0447\u0442\u043e \u0434\u043b\u044f d=x+1 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 e, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e A<=B, \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 y. \u0422\u043e \u0435\u0441\u0442\u044c, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 e \u043f\u043e\u043a\u0430 \u0438\u0434\u0435\u043c \u043f\u043e d \u0438 \u044d\u0442\u043e \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442, \u0447\u0442\u043e \u043c\u044b \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u043c. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f d \u0438 e \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f, \u043e\u0431\u0449\u0438\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u043d\u0438\u043c \u0437\u0430\u0439\u043c\u0435\u0442 \u0432\u0440\u0435\u043c\u044f O(n). \u042d\u0442\u043e \u0438\u0434\u0435\u044f \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0434\u0432\u0443\u0445 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439.  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale4( int n ) {     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)             for (int c=b+1; c<=n; c++)             {                 int e = c+1;                 for (int d=c+1; d<=n; d++)                 {                     long long a5 = (long long)a*a*a*a*a;                     long long b5 = (long long)b*b*b*b*b;                     long long c5 = (long long)c*c*c*c*c;                     long long d5 = (long long)d*d*d*d*d;                     long long sum = a5+b5+c5+d5;                      while (e<n && (long long)e*e*e*e*e < sum) e++;                      if (sum == (long long)e*e*e*e*e)                         if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                             printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }             } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u041a\u043e\u0434\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0434\u043b\u044f \u0431\u0438\u043d\u043f\u043e\u0438\u0441\u043a\u0430, \u0430 \u043f\u043e\u043b\u044c\u0437\u044b \u0431\u043e\u043b\u044c\u0448\u0435.  <\/p>\n\n\n\n\n\n\n
    n<\/th>\n\u0412\u0440\u0435\u043c\u044f #1<\/th>\n\u0412\u0440\u0435\u043c\u044f #2<\/th>\n\u0412\u0440\u0435\u043c\u044f #3<\/th>\n\u0412\u0440\u0435\u043c\u044f #4<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n<\/tr>\n<\/table>\n
      \u0418\u0437-\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0441\u043a\u0440\u044b\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u043e\u0431\u0433\u043e\u043d\u044f\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 #2 \u0437\u0430 O(n4<\/sup>log n) \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 n \u043f\u043e\u0440\u044f\u0434\u043a\u0430 500. \u0415\u0433\u043e, \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0436\u0435, \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044f \u043f\u044f\u0442\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u0434\u0443\u043c\u0430\u043d\u043d\u043e, \u043d\u043e \u043c\u044b \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u043b\u0430\u0442\u044c.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f #2, \u0442\u0440\u0435\u0431\u0443\u0435\u0442 O(1) \u043f\u0430\u043c\u044f\u0442\u0438. \u0414\u0430, \u043d\u0430\u0445\u043e\u0434\u0438\u0442.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0434\u0430\u043b\u0435\u043a\u043e \u043d\u0435 \u0441\u0430\u043c\u044b\u0439 \u043e\u043f\u0442\u0438\u043c\u0443\u043c, \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0441\u043a\u0440\u044b\u0442\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #5 \u0437\u0430 O(n3<\/sup>)<\/h1>\n
      \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0437\u0432\u0438\u0432\u0430\u0442\u044c \u0438\u0434\u0435\u044e \u0441 \u0434\u0432\u0443\u043c\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438, \u0430 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u0435 \u0432 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u043f\u0435\u0440\u0435\u0432\u0435\u0440\u043d\u0435\u043c \u0432\u0432\u0435\u0440\u0445 \u0434\u043d\u043e\u043c. \u041f\u0443\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 A+B=C, \u043f\u0440\u0438\u0447\u0435\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 A, B, C \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c n(A), n(B), n© \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0438\u0445 \u0432\u044b\u0431\u0440\u0430\u0442\u044c. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u043a\u0430\u043a\u043e\u0435-\u043d\u0438\u0431\u0443\u0434\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 C, \u0430 \u0432\u0441\u0435 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043b\u044f A \u0438 B \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u043f\u043e \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044e. \u0422\u043e\u0433\u0434\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0431\u0435\u0436\u0430\u0442\u044c \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c A \u0438 B \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0432\u0443\u0445 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0438 \u0437\u0430 O(n(A)+n(B)) \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0434\u043b\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0421! \u0410 \u0438\u043c\u0435\u043d\u043d\u043e: \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e A \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 B, \u043f\u043e\u043a\u0430 A+B>C. \u041a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0442\u0430\u043d\u0435\u0442 A+B<=C, \u0434\u0430\u043b\u044c\u0448\u0435 B \u0441\u043c\u044b\u0441\u043b\u0430 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0442\u044c \u043d\u0435\u0442. \u0422\u043e\u0433\u0434\u0430 \u043c\u044b \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c A \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f B. \u0412\u0435\u0441\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0437\u0430\u0439\u043c\u0435\u0442 \u0432\u0440\u0435\u043c\u044f O( n(A) log n(A) + n(B) log n(B) + (n(A)+n(B)) n© ).<\/p>\n
      \u0414\u043b\u044f \u0441\u043b\u0443\u0447\u0430\u044f, \u043a\u043e\u0433\u0434\u0430 A \u0438 B \u2014 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043e\u0434\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e C \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0435 A \u0438 B \u0432\u0441\u0442\u0440\u0435\u0442\u044f\u0442\u0441\u044f (\u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443, \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043e\u0431\u0449\u043d\u043e\u0441\u0442\u0438, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e A<B).<\/p>\n
      \u0422\u0435\u043f\u0435\u0440\u044c \u0432 \u043d\u0430\u0448\u0435\u043c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c (a5<\/sup> + b5<\/sup>) \u0437\u0430 A, (c5<\/sup> + d5<\/sup>) \u0437\u0430 B, \u0430 e5<\/sup> \u0437\u0430 \u0421. \u0418 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u0434:  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale5( int n ) {     vector< pair< long long, int > > vec;     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)         {             long long a5 = (long long)a*a*a*a*a;             long long b5 = (long long)b*b*b*b*b;             if (a5 + b5 < (long long)n*n*n*n*n) \/\/ avoid overflow for n<=5000                 vec.push_back( make_pair( a5+b5, (a<<16)+b ) );         }     sort( vec.begin(), vec.end() );      for (int e=1; e<=n; e++)     {         long long e5 = (long long)e*e*e*e*e;         int i = 0, j = (int)vec.size()-1;         while( i < j )         {             while ( i < j && vec[i].first + vec[j].first > e5 ) j--;             if ( vec[i].first + vec[j].first == e5 )             {                 int a = (vec[i].second >> 16);                 int b = (vec[i].second & ((1<<16)-1));                 int c = (vec[j].second >> 16);                 int d = (vec[j].second & ((1<<16)-1));                 if (b < c && gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                     printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );             }             i++;         }     } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u0430\u0440 (a,b) (\u0438 (c,d)) \u0443 \u043d\u0430\u0441 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 n2<\/sup>, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0430\u0439\u043c\u0435\u0442 O(n2<\/sup> log n), \u0430 \u0434\u0430\u043b\u044c\u0448\u0435\u0439\u0448\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u2014 O(n3<\/sup>). \u0418\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u0442\u044b\u0439 \u043a\u0443\u0431.<\/p>\n
      \u0423\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u0435<\/b>. \u041d\u0430\u0439\u0434\u0438\u0442\u0435 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043e\u0448\u0438\u0431\u043a\u0443 \u0432 \u043a\u043e\u0434\u0435 \u0432\u044b\u0448\u0435.  <\/p>\n
    \u041f\u043e\u0434\u0443\u043c\u0430\u0439\u0442\u0435 \u043f\u0430\u0440\u0443 \u043c\u0438\u043d\u0443\u0442 \u043f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043e\u0442\u0432\u0435\u0442.<\/b><\/p>\n
    \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u043f\u0430\u0441\u0442\u044c\u0441\u044f \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u0441\u0443\u043c\u043c\u044b \u0438 \u0442\u043e\u0433\u0434\u0430 \u0434\u0432\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430. \u041d\u043e \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0432\u0441\u0435 \u0440\u0430\u0437\u043d\u044b\u0435 \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0440\u0430\u0441\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u0439: \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0443\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f, \u0442\u043e x^5+y^5 = z^5+t^5 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 x, y, z, t \u0438 \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043a\u043e\u043d\u0442\u0440\u043f\u0440\u0438\u043c\u0435\u0440 \u043a \u044d\u0442\u043e\u0439 \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0435<\/a>. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0430\u043c\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2014 \u044d\u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b.  <\/div>\n<\/div>\n
      <\/p>\n\n\n\n\n\n\n\n\n
    n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n<\/tr>\n
    2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n<\/tr>\n
    5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n<\/tr>\n<\/table>\n
      \u0417\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0437\u0430\u0442\u0430\u0449\u0438\u0442\u044c n=5000 \u0437\u0430 \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u043f\u0430\u0440 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0443\u0436\u043d\u044b \u0434\u043b\u044f \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e, \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0435.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0441\u043a\u0440\u044b\u0442\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430, \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043e n \u043f\u043e\u0440\u044f\u0434\u043a\u0430 5000, \u0436\u0440\u0435\u0442 \u0430\u0436 O(n2<\/sup>) \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #6 \u0437\u0430 O(n4<\/sup> log n) \u0441 \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0439 \u0441\u043a\u0440\u044b\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439<\/h1>\n
      \u0412\u043d\u0435\u0437\u0430\u043f\u043d\u043e. \u0421 \u043f\u043e\u0434\u0430\u0447\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f erwins22<\/a> \u0438\u0437 \u044d\u0442\u043e\u0433\u043e<\/a> \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0441\u0442\u0430\u0442\u043a\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u0440\u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u043f\u044f\u0442\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0430 11. \u0422\u043e \u0435\u0441\u0442\u044c, \u043a\u0430\u043a\u0438\u0435 a \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 x5<\/sup>=a mod 11. \u041e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f a \u2014 \u044d\u0442\u043e 0, 1 \u0438 -1 (mod 11) (\u043f\u0440\u043e\u0432\u0435\u0440\u044c\u0442\u0435 \u0441\u0430\u043c\u0438 \u0438 \u0443\u0431\u0435\u0434\u0438\u0442\u0435\u0441\u044c).<\/p>\n
      \u0422\u043e\u0433\u0434\u0430 \u0432 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0435 a5<\/sup> + b5<\/sup> + c5<\/sup> + d5<\/sup> = e5<\/sup> \u0435\u0434\u0438\u043d\u0438\u0446 \u0438 \u043c\u0438\u043d\u0443\u0441 \u0435\u0434\u0438\u043d\u0438\u0446 \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u043e \u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e (\u043e\u043d\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0430 \u0443\u0440\u0430\u0432\u043d\u043e\u0432\u0435\u0441\u0438\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u0447\u0435\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0448\u043b\u0430\u0441\u044c), \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e \u043e\u0434\u043d\u043e \u0438\u0437 \u0447\u0438\u0441\u0435\u043b a, b, c, d, e \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u043e \u0441 0 \u0434\u043e \u043c\u043e\u0434\u0443\u043b\u044e 11, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 11. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u043d\u0435\u0441\u0435\u043c \u0435\u0433\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432:<\/p>\n
      (a5<\/sup> + b5<\/sup>) + (c5<\/sup> + d5<\/sup>) = e5<\/sup>; e = 0 mod 11<\/p>\n
      (e5<\/sup> \u2014 a5<\/sup>) \u2014 (b5<\/sup> + c5<\/sup>) = d5<\/sup>; d = 0 mod 11<\/p>\n
      \u0412\u044b \u043d\u0435 \u043f\u043e\u0432\u0435\u0440\u0438\u0442\u0435, \u043d\u043e \u0435\u0441\u043b\u0438 \u0447\u0438\u0441\u043b\u043e x \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 11, \u0442\u043e \u0447\u0438\u0441\u043b\u043e x5<\/sup> \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 161051. \u0417\u043d\u0430\u0447\u0438\u0442, \u043d\u0430 161051 \u0434\u043e\u043b\u0436\u043d\u0430 \u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0438 \u043b\u0435\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0432\u044b\u0448\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432. \u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0432 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f\u0445 \u0432\u044b\u0448\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0443\u0436\u0435 \u0437\u0430\u0431\u043e\u0442\u043b\u0438\u0432\u043e \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u044b \u0432 \u043f\u0430\u0440\u044b \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0441\u043a\u043e\u0431\u043e\u043a. \u0422\u0435\u043f\u0435\u0440\u044c, \u0435\u0441\u043b\u0438 \u043c\u044b \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u0441\u043a\u043e\u0431\u043a\u0443, \u0442\u043e \u0432\u0442\u043e\u0440\u0430\u044f \u0441\u043a\u043e\u0431\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u0438\u0437 \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 161051 \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432 \u043f\u0440\u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u043d\u0430 161051. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0438\u0437 O(n2<\/sup>) \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u043a\u043e\u0431\u043e\u043a \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c<\/i> \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f O(n2<\/sup>\/161051) \u0432\u0442\u043e\u0440\u044b\u0445. \u0415\u0441\u043b\u0438 \u043c\u044b \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0435\u0440\u0435\u0431\u0435\u0440\u0435\u043c \u0438\u0445 \u0432\u0441\u0435 \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0442\u043e\u0447\u043d\u043e\u0439 \u043f\u044f\u0442\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0431\u0438\u043d\u043e\u0438\u0441\u043a\u043e\u043c \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043f\u044f\u0442\u044b\u0445 \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439) \u2014 \u0442\u043e \u043d\u0430\u0439\u0434\u0435\u043c \u0432\u0441\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430 O(n4<\/sup> log n\/161051). \u041a\u043e\u0434:  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale5( int n ) {     vector< pair< long long, int > > vec;     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)         {             long long a5 = (long long)a*a*a*a*a;             long long b5 = (long long)b*b*b*b*b;             if (a5 + b5 < (long long)n*n*n*n*n) \/\/ avoid overflow for n<=5000                 vec.push_back( make_pair( a5+b5, (a<<16)+b ) );         }      vector< pair< long long, int > > pows;     for (int a=1; a<=n; a++)         pows.push_back( make_pair( (long long)a*a*a*a*a, a ) );      \/\/ a^5 + b^5 + c^5 + d^5 = e^5     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)         {             long long a5 = (long long)a*a*a*a*a;             long long b5 = (long long)b*b*b*b*b;             long long rem = (z - (a5+b5)%z)%z;             for (int i=0; i<(int)vec[rem].size(); i++)             {                 long long sum = a5 + b5 + vec[rem][i].first;                 vector< pair< long long, int > >::iterator                     it = lower_bound( pows.begin(), pows.end(), make_pair( sum, 0 ) );                 if (it != pows.end() && sum == it->first)                 {                     int c = (vec[rem][i].second >> 16);                     int d = (vec[rem][i].second & ((1<<16)-1));                     int e = it->second;                     if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                         printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }             }         }      \/\/ e^5 - a^5 - b^5 - c^5 = d^5     for (int e=1; e<=n; e++)         for (int a=1; a<e; a++)         {             long long e5 = (long long)e*e*e*e*e;             long long a5 = (long long)a*a*a*a*a;             long long rem = (e5-a5)%z;             for (int i=0; i<(int)vec[rem].size(); i++)                 if (e5-a5 > vec[rem][i].first)                 {                     long long sum = e5 - a5 - vec[rem][i].first;                     vector< pair< long long, int > >::iterator                         it = lower_bound( pows.begin(), pows.end(), make_pair( sum, 0 ) );                     if (it != pows.end() && sum == it->first)                     {                         int b = (vec[rem][i].second >> 16);                         int c = (vec[rem][i].second & ((1<<16)-1));                         int d = it->second;                         if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                             printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                     }                 }         } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u0412\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f:  <\/p>\n\n\n\n\n\n\n\n\n
    n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n#6<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n129ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n140ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n375ms<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n2559ms<\/td>\n<\/tr>\n
    2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n38s<\/td>\n<\/tr>\n
    5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n28m<\/td>\n<\/tr>\n<\/table>\n
      \u0418\u0437 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0434\u043b\u044f n=500 \u0438 n=1000 \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u0430\u0436\u0435 \u043e\u0431\u0433\u043e\u043d\u044f\u0435\u0442 \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u043e\u0435. \u041d\u043e \u0437\u0430\u0442\u0435\u043c \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0441\u0435 \u0436\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u0431\u0433\u043e\u043d\u044f\u0442\u044c. \u0410\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u043e\u043d\u0430 \u0442\u0430\u043a\u0430\u044f \u2014 \u0435\u0435 \u043d\u0435 \u043e\u0431\u043c\u0430\u043d\u0435\u0448\u044c.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u043e\u0447\u0435\u043d\u044c \u043c\u043e\u0449\u043d\u043e\u0435 \u043e\u0442\u0441\u0435\u0447\u0435\u043d\u0438\u0435.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430, \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e \u043a\u0430\u043a \u043f\u0440\u0438\u043a\u0440\u0443\u0442\u0438\u0442\u044c \u044d\u0442\u0443 \u0438\u0434\u0435\u044e \u043a \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u0440\u0435\u0448\u0435\u043d\u0438\u044e.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #7 \u0437\u0430 O(n3<\/sup>) co 128-\u0431\u0438\u0442\u043d\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438<\/h1>\n
      \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043a\u0430 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0437\u0430\u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e \u0442\u0440\u044e\u043a\u0438 \u0441 \u043c\u043e\u0434\u0443\u043b\u044f\u043c\u0438 (\u043c\u044b \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0437 \u0432\u0441\u043f\u043e\u043c\u043d\u0438\u043c \u0447\u0443\u0442\u044c \u043f\u043e\u0437\u0436\u0435!) \u0438 \u043f\u0435\u0440\u0435\u0434\u0435\u043b\u0430\u0435\u043c \u043d\u0430\u0448\u0435 \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u043e \u043c\u043e\u0433\u043b\u043e \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0434\u043b\u044f n>5000. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c 128-\u0431\u0438\u0442\u043d\u044b\u0435 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430.  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    typedef unsigned long long uint64; typedef pair< uint64, uint64 > uint128;  uint128 operator+ (const uint128 & a, const uint128 & b) {     uint128 re = make_pair( a.first + b.first, a.second + b.second );     if ( re.second < a.second ) re.first++;     return re; }  uint128 operator- (const uint128 & a, const uint128 & b) {     uint128 re = make_pair( a.first - b.first, a.second - b.second );     if ( re.second > a.second ) re.first--;     return re; }  uint128 power5( int x ) {     uint64 x2 = (uint64)x*x;     uint64 x3 = (uint64)x2*x;     uint128 re = make_pair( (uint64)0, (uint64)0 );     uint128 cur = make_pair( (uint64)0, x3 );     for (int i=0; i<63; i++)     {         if ((x2>>i)&1) re = re + cur;         cur = cur + cur;     }     return re; }  void tale7( int n ) {     vector< pair< uint128, int > > vec = vector< pair< uint128, int > >( n*n\/2 );     uint128 n5 = power5( n );     int ind = 0;     for (int a=1; a<=n; a++)         for (int b=a+1; b<=n; b++)         {             uint128 a5 = power5( a );             uint128 b5 = power5( b );             if (a5 + b5 < n5)                 vec[ind++] = make_pair( a5+b5, (a<<16)+b );         }     sort( vec.begin(), vec.begin()+ind );      for (int e=1; e<=n; e++)     {         uint128 e5 = power5( e );         int i = 0, j = ind-1;         while( i < j )         {             while ( i < j && vec[i].first + vec[j].first > e5 ) j--;             if ( vec[i].first + vec[j].first == e5 )             {                 int a = (vec[i].second >> 16);                 int b = (vec[i].second & ((1<<16)-1));                 int c = (vec[j].second >> 16);                 int d = (vec[j].second & ((1<<16)-1));                 if (b < c && gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                     printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );             }             i++;         }     } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0434\u043e\u043f\u0438\u0441\u0430\u0442\u044c \u2014 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043f\u044f\u0442\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0415\u0449\u0435 \u0435\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435, \u0432 \u044d\u0442\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u043e\u043d\u043e \u043d\u0435 \u043d\u0443\u0436\u043d\u043e, \u043d\u043e \u043e\u043d\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u043f\u043e\u0437\u0436\u0435. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0443\u0441\u0442\u044c \u0431\u0443\u0434\u0435\u0442. \u0422\u0430\u043a \u043a\u0430\u043a 128-\u0431\u0438\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e \u043a\u0430\u043a pair, \u0442\u0430\u043c \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <, >, =, \u043f\u0440\u0438\u0447\u0435\u043c \u043e\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a, \u043a\u0430\u043a \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e.<\/p>\n
      \u0412 \u0441\u0430\u043c\u043e\u043c \u043d\u0430\u0447\u0430\u043b\u0435 \u043c\u044b \u0441\u0440\u0430\u0437\u0443 \u0437\u0430\u0434\u0430\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0432\u0435\u043a\u0442\u043e\u0440\u0430. \u041d\u0435 \u0442\u043e, \u0447\u0442\u043e\u0431\u044b \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u043f\u0440\u043e\u0441\u0442\u043e \u043c\u043d\u0435 \u043f\u043e\u043a\u0430 \u043b\u0435\u043d\u044c \u0440\u0430\u0441\u0447\u0435\u0445\u043b\u044f\u0442\u044c 64-\u0431\u0438\u0442\u043d\u044b\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440, \u0430 \u043d\u0430 32 \u0431\u0438\u0442\u0430\u0445 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e 2\u0413\u0431 \u043f\u0430\u043c\u044f\u0442\u0438. \u0421\u0435\u0439\u0447\u0430\u0441 \u0434\u043b\u044f n=10000 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u043a\u043e\u043b\u043e 1.2\u0413\u0431 \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440. \u0415\u0441\u043b\u0438 \u0440\u0430\u0441\u0448\u0438\u0440\u044f\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 \u0447\u0435\u0440\u0435\u0437 push_back, \u0442\u043e \u043e\u043d \u043f\u043e\u0434 \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u043d\u0435\u0446 \u0437\u0430\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 2\u0413\u0431 \u043f\u0440\u0438 \u0440\u0435\u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0438 (\u0447\u0442\u043e\u0431\u044b \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c\u0441\u044f \u0441 \u0434\u043b\u0438\u043d\u044b N \u0434\u043e 2*N \u043d\u0443\u0436\u043d\u043e 3*N \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438).  <\/p>\n\n\n\n\n\n\n\n\n\n
    n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n#6<\/th>\n#7<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n129ms<\/td>\n20ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n140ms<\/td>\n105ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n375ms<\/td>\n1014ms<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n2559ms<\/td>\n7096ms<\/td>\n<\/tr>\n
    2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n38s<\/td>\n52s<\/td>\n<\/tr>\n
    5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n28m<\/td>\n13m<\/td>\n<\/tr>\n
    10000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n89m<\/td>\n<\/tr>\n<\/table>\n
      \u041c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0437\u0430\u043c\u0435\u0434\u043b\u0438\u043b\u0430\u0441\u044c \u043f\u043e\u0447\u0442\u0438 \u0440\u043e\u0432\u043d\u043e \u0432 2 \u0440\u0430\u0437\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f #5, \u0437\u0430\u0442\u043e \u043c\u044b \u043f\u043e\u043a\u043e\u0440\u0438\u043b\u0438 \u043d\u043e\u0432\u0443\u044e \u043d\u0435\u043f\u0440\u0438\u0441\u0442\u0443\u043f\u043d\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 n=10000!<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f n>5000.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 2 \u0440\u0430\u0437\u0430 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f #5, \u0436\u0440\u0435\u0442 \u043a\u0443\u0447\u0443 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #8 \u0437\u0430 O(n3<\/sup>) \u0441 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u043a\u0440\u044b\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439<\/h1>\n
      \u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c \u043e\u043f\u044f\u0442\u044c \u043f\u0440\u043e \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u0440\u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u043d\u0430 11. \u0418\u043c\u0435\u0435\u043c \u0434\u0432\u0430 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430:<\/p>\n
      (a5<\/sup> + b5<\/sup>) + (c5<\/sup> + d5<\/sup>) = e5<\/sup>; e = 0 mod 11<\/p>\n
      (e5<\/sup> \u2014 a5<\/sup>) \u2014 (b5<\/sup> + c5<\/sup>) = d5<\/sup>; d = 0 mod 11<\/p>\n
      \u041d\u0430\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u043f\u044f\u0442\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e 11 \u0432\u0441\u0435\u0433\u0434\u0430 \u0438\u043c\u0435\u044e\u0442 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 0, 1 \u0438\u043b\u0438 -1. \u0421\u043d\u0438\u043c\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0432\u0438\u0434\u0430 a < b < c < d \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u043c \u0447\u0438\u0441\u043b\u0430\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u0441\u043a\u043e\u0431\u043a\u0438 \u0432 \u0434\u0440\u0443\u0433\u0443\u044e. \u0422\u043e\u0433\u0434\u0430 \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c (\u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u0435\u043c \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432), \u0447\u0442\u043e \u0438\u0445 \u0432\u0441\u0435\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u0441\u043a\u043e\u0431\u043e\u043a \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430 0 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e 11. \u041d\u0443 \u0438 \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0432\u0441\u0435 \u043f\u0430\u0440\u044b \u0447\u0438\u0441\u0435\u043b \u043e\u0442 1 \u0434\u043e n, \u043d\u0430\u0439\u0442\u0438 \u0441\u0443\u043c\u043c\u0443 \u0438 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u0438\u0445 \u043f\u044f\u0442\u044b\u0445 \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439 \u0438 \u0437\u0430\u043f\u043e\u043c\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043d\u0430 11. \u0410 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0430\u0440\u044b \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0442\u044c.<\/p>\n
      \u041c\u043e\u0436\u043d\u043e \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0444\u0430\u043a\u0442: \u0447\u0438\u0441\u043b\u043e \u0442\u0430\u043a\u0438\u0445 \u043f\u0430\u0440 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 51\/121 \u043e\u0442 \u043e\u0431\u0449\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043f\u0430\u0440 (\u043f\u043e\u0434\u0443\u043c\u0430\u0439\u0442\u0435 \u043f\u043e\u0447\u0435\u043c\u0443 \u044d\u0442\u043e \u0442\u0430\u043a). \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0442\u0430\u043a\u0438\u0445 \u043f\u0430\u0440 (\u0434\u043b\u044f \u0441\u0443\u043c\u043c\u044b \u0438 \u0434\u043b\u044f \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u0438), \u0447\u0442\u043e \u0434\u0430\u0441\u0442 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u0442\u043e\u043b\u044c\u043a\u043e 102\/121. \u041d\u0443, 15% \u2014 \u044d\u0442\u043e \u0442\u043e\u0436\u0435 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u0435. \u0417\u0430\u0442\u043e \u0434\u0430\u043b\u0435\u0435 \u043d\u0430\u043c \u043f\u043e \u044d\u0442\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u0447\u0443\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u0431\u0435\u0433\u0430\u0442\u044c.<\/p>\n
      \u041d\u0443 \u0438, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u0441\u0430\u043c\u044b\u0435 \u0445\u043e\u0440\u043e\u0448\u0438\u0435 \u043d\u043e\u0432\u043e\u0441\u0442\u0438: \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u043c \u0438\u043c\u0435\u0435\u043c \u0441\u043c\u044b\u0441\u043b \u043e\u0434\u043d\u0443 \u0438\u0437 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u0430\u043c\u0430\u044f \u0432\u043d\u0435\u0448\u043d\u044f\u044f \u0432 \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438) \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0441 \u0448\u0430\u0433\u043e\u043c \u0432 11. \u041f\u043b\u043e\u0445\u0438\u0435 \u043d\u043e\u0432\u043e\u0441\u0442\u0438 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u043e\u0431\u0430 \u0432\u0438\u0434\u0430 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432. \u0421\u0430\u043c\u043e\u0435 \u043f\u0435\u0447\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u043e \u0432\u0441\u0435\u043c \u044d\u0442\u043e\u043c: \u0443\u0432\u044b, \u044d\u0442\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0432\u0441\u0435\u0433\u043e \u0432 11 \u0440\u0430\u0437 (\u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0444\u0430\u043a\u0442), \u0432\u043c\u0435\u0441\u0442\u043e 115<\/sup> \u0440\u0430\u0437, \u043a\u0430\u043a \u0432 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 #6.  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    void tale8( int n ) {     vector< pair< uint128, pair< int, int > > > vec_p, vec_m;     uint128 n5 = power5( n );     for (int a=1; a<=n; a++)         for (int b=1; b<a; b++)         {             uint128 a5 = power5( a );             uint128 b5 = power5( b );             int A = a%11;             int B = b%11;             int A5 = (A*A*A*A*A)%11;             int B5 = (B*B*B*B*B)%11;             if ( (A5+B5)%11 == 0 )                 vec_p.push_back( make_pair( a5+b5, make_pair( a, b ) ) );             if ( (A5-B5+11)%11 == 0)                 vec_m.push_back( make_pair( a5-b5, make_pair( a, b ) ) );         }      sort( vec_p.begin(), vec_p.end() );     sort( vec_m.begin(), vec_m.end() );      \/\/ (a^5 + b^5) + (c^5 + d^5) = e^5     for (int e=11; e<=n; e+=11)     {         uint128 e5 = power5( e );         int i = 0, j = (int)vec_p.size()-1;         while( i < j )         {             while ( i < j && vec_p[i].first + vec_p[j].first > e5 ) j--;             if ( vec_p[i].first + vec_p[j].first == e5 )             {                 int a = vec_p[i].second.first;                 int b = vec_p[i].second.second;                 int c = vec_p[j].second.first;                 int d = vec_p[j].second.second;                 if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                     printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );             }             i++;         }     }      \/\/ (e^5 - a^5) - (b^5 + c^5) = d^5     for (int d=11; d<=n; d+=11)     {         uint128 d5 = power5( d );         int i = 0, j = 0, mx_i = (int)vec_m.size(), mx_j = (int)vec_p.size();         while (i < mx_i && j < mx_j)         {             while (j < mx_j && vec_m[i].first > vec_p[j].first && vec_m[i].first - vec_p[j].first > d5) j++;             if ( j < mx_j && vec_m[i].first > vec_p[j].first && vec_m[i].first - vec_p[j].first == d5 )             {                 int e = vec_m[i].second.first;                 int a = vec_m[i].second.second;                 int b = vec_p[j].second.first;                 int c = vec_p[j].second.second;                 if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                     printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );             }             i++;         }     } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u0422\u0443\u0442 \u0441 \u0440\u0435\u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0435\u0439 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u043f\u043e\u0432\u0435\u0437\u043b\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0434\u043b\u044f n=10000 \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 2\u0413\u0431.  <\/p>\n\n\n\n\n\n\n\n\n\n
    n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n#6<\/th>\n#7<\/th>\n#8<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n129ms<\/td>\n20ms<\/td>\n16ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n140ms<\/td>\n105ms<\/td>\n49ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n375ms<\/td>\n1014ms<\/td>\n472ms<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n2559ms<\/td>\n7096ms<\/td>\n2110ms<\/td>\n<\/tr>\n
    2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n38s<\/td>\n52s<\/td>\n13s<\/td>\n<\/tr>\n
    5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n28m<\/td>\n13m<\/td>\n161s<\/td>\n<\/tr>\n
    10000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n89m<\/td>\n20m<\/td>\n<\/tr>\n<\/table>\n
      \u0423\u0432\u044b \u0438 \u0430\u0445, \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0443\u0441\u043a\u043e\u0440\u0438\u043b\u0430\u0441\u044c \u0432\u0441\u0435\u0433\u043e \u0432 4,5 \u0440\u0430\u0437. \u0412\u0438\u0434\u0430\u0442\u044c, \u043c\u043d\u043e\u0433\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441\u0438\u043b\u044c\u043d\u043e \u043f\u043e\u0434\u043f\u043e\u0440\u0442\u0438\u043b\u0438 \u0441\u043a\u0440\u044b\u0442\u0443\u044e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443. \u041d\u0443 \u043d\u0438\u0447\u0435\u0433\u043e, \u0442\u0443\u0442 \u0435\u0449\u0435 \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0440 \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439. \u0421\u0430\u043c\u0430\u044f \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441\u0435\u0439\u0447\u0430\u0441: \u0434\u0438\u043a\u043e\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438. \u0415\u0441\u043b\u0438 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043b\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u043a\u043e\u0440\u0434\u0430 n \u0443\u0436\u0435 \u0442\u0435\u0440\u043f\u0438\u043c\u043e, \u0442\u043e \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u043c\u044b \u0443\u0436\u0435 \u043d\u0435 \u0432\u043b\u0435\u0437\u0430\u0435\u043c.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u043d\u0430\u0432\u0435\u0440\u043d\u043e, \u0441\u0430\u043c\u043e\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438\u0437 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0432\u0441\u0435 \u0435\u0449\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #9 \u0437\u0430 O(n3<\/sup>log n) \u0441 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u0438 O(n)<\/h1>\n
      \u041a\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438? \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0442\u0440\u044e\u043a\u043e\u043c, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u043c \u0437\u0434\u0435\u0441\u044c<\/a>. \u0410 \u0438\u043c\u0435\u043d\u043d\u043e: \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u043a\u0430\u043a\u043e\u0435-\u043d\u0438\u0431\u0443\u0434\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e p, \u0431\u043e\u043b\u044c\u0448\u0435\u0435 n, \u043d\u043e \u043d\u0435 \u043d\u0430\u043c\u043d\u043e\u0433\u043e. H\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0435\u0440\u0432\u043e\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c (\u0432\u0442\u043e\u0440\u043e\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e):<\/p>\n
      (a5<\/sup> + b5<\/sup>) + (c5<\/sup> + d5<\/sup>) = e5<\/sup>; e = 0 mod 11<\/p>\n
      \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u0443\u0441\u0442\u044c (a5<\/sup> + b5<\/sup>) = w mod p \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e w \u043e\u0442 0 \u0434\u043e p-1. \u0422\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e \u043f\u0430\u0440 (a,b), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0442 \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u2014 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u044d\u0442\u043e, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0431\u0435\u0440\u0435\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 a \u043e\u0442 1 \u0434\u043e n. \u0422\u043e\u0433\u0434\u0430, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 b, \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u0448\u0438\u0442\u044c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 b5<\/sup> = (w \u2014 a5<\/sup>) = u mod p. \u0418 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0443 \u044d\u0442\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0421\u043b\u0435\u0434\u0443\u0435\u0442 \u044d\u0442\u043e \u0432\u043e\u0442 \u0438\u0437 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u044b \u043d\u0430 e-maxx<\/a>. \u0422\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e:<\/p>\n
      <\/p>\n
      \u0422\u043e \u0435\u0441\u0442\u044c, \u0432\u0441\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0443 \u043d\u0430\u0441 gcd( 5, phi( p ) ) = gcd( 5, p-1 ). \u041e\u0442\u0441\u044e\u0434\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 p=5q+1, \u0442\u043e \u0443 \u043d\u0430\u0441 5 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 (\u0438\u043b\u0438 \u043d\u0438 \u043e\u0434\u043d\u043e\u0433\u043e), \u0430 \u0432 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u2014 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435, \u0447\u0435\u043c \u043e\u0434\u043d\u043e.<\/p>\n
      (\u041a\u0441\u0442\u0430\u0442\u0438, \u044f \u043f\u043e\u043d\u044f\u0442\u0438\u044f \u043d\u0435 \u0438\u043c\u0435\u044e \u043e\u0442\u043a\u0443\u0434\u0430 \u044d\u0442\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u0438 \u043a\u0430\u043a \u043e\u043d\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442. \u0415\u0441\u043b\u0438 \u043a\u0442\u043e \u0437\u043d\u0430\u0435\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a, \u0433\u0434\u0435 \u044d\u0442\u043e \u0434\u043e\u0445\u043e\u0434\u0447\u0438\u0432\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u043e \u2014 \u043f\u0440\u043e\u0441\u044c\u0431\u0430 \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0441\u0441\u044b\u043b\u043a\u043e\u0439.)<\/p>\n
      \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u043e\u043f\u0440\u043e\u0441 \u2014 \u043a\u0430\u043a \u043d\u0430\u0439\u0442\u0438 \u0434\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e u \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 b? \u0427\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u0435\u0434\u0438\u043d\u043e\u0440\u0430\u0437\u043e\u0432\u043e, \u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e \u2014 \u043d\u0443\u0436\u043d\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b. \u041d\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u044b b \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 u, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e b \u043d\u0430\u0439\u0442\u0438 u, \u0438 \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0432 \u0442\u0430\u0431\u043b\u0438\u0447\u043a\u0443: \u0432\u043e\u0442 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e u \u2014 \u0442\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 b.<\/p>\n
      \u0414\u0430\u043b\u0435\u0435, \u0434\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e w \u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e e5<\/sup>, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c, \u0447\u0442\u043e (c5<\/sup> + d5<\/sup>) = (e5<\/sup> \u2014 w) mod p. \u0422\u0443\u0442 \u0442\u043e\u0436\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0440, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e.<\/p>\n
      \u0422\u043e \u0435\u0441\u0442\u044c, \u0434\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e w \u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e e \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c (\u043a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0437\u0434\u0435\u0441\u044c \u0432\u044b\u043b\u0435\u0437\u0430\u0435\u0442 \u043b\u0438\u0448\u043d\u0438\u0439 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0432 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0435), \u043f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u0440\u043e\u0439\u0442\u0438\u0441\u044c \u0434\u0432\u0443\u043c\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 w \u0438 e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(n), \u043e\u0431\u0449\u0430\u044f \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f O(n3<\/sup>log n).<\/p>\n
      \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043f\u0440\u043e\u0431\u043d\u044b\u0439 \u0441\u0442\u0440\u0430\u0448\u043d\u044b\u0439 \u043a\u043e\u0434:  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    bool is_prime( int x ) {     if (x<2) return false;     for (int a=2; a*a<=x; a++)         if (x%a==0)             return false;     return true; }  void tale9( int n ) {     int p = n+1;     while ( p%5==1 || !is_prime( p ) ) p++;      vector< int > sols = vector< int >( p, -1 );     for (int i=1; i<=n; i++)     {         uint64 tmp = ((uint64)i*i)%p;         tmp = (((tmp*tmp)%p)*i)%p;         sols[(unsigned int)tmp] = i;     }      for (int w=0; w<p; w++)     {         \/\/ (a^5 + b^5) + (c^5 + d^5) = e^5         \/\/ (a^5 + b^5) = w  (mod p)         vector< pair< uint128, pair< int, int > > > vec1;          for (int a=1; a<=n; a++)         {             uint64 a5p = ((uint64)a*a)%p;             a5p = ((a5p*a5p)%p*a)%p;             int b = sols[ (w - a5p + p)%p ];             if (b!=-1 && b<a)             {                 uint128 a5 = power5( a );                 uint128 b5 = power5( b );                 int A = a%11, A5 = (A*A*A*A*A)%11;                 int B = b%11, B5 = (B*B*B*B*B)%11;                 if ( (A5+B5)%11 == 0 )                     vec1.push_back( make_pair( a5+b5, make_pair( a, b ) ) );             }         }          sort( vec1.begin(), vec1.end() );          for (int e=11; e<=n; e+=11)         {             \/\/ (a^5 + b^5) + (c^5 + d^5) = e^5             \/\/ (a^5 + b^5) = w  (mod p)             \/\/ (c^5 + d^5) = (e^5 - w) = q  (mod p)             uint64 e5p = ((uint64)e*e)%p;             e5p = ((e5p*e5p)%p*e)%p;             int q = (int)((e5p - w + p)%p);             vector< pair< uint128, pair< int, int > > > vec2;              for (int c=1; c<=n; c++)             {                 uint64 c5p = ((uint64)c*c)%p;                 c5p = ((c5p*c5p)%p*c)%p;                 int d = sols[ (q - c5p + p)%p ];                 if (d!=-1 && d<c)                 {                     uint128 c5 = power5( c );                     uint128 d5 = power5( d );                     int C = c%11, C5 = (C*C*C*C*C)%11;                     int D = d%11, D5 = (D*D*D*D*D)%11;                     if ( (C5+D5)%11 == 0 )                         vec2.push_back( make_pair( c5+d5, make_pair( c, d ) ) );                 }             }              sort( vec2.begin(), vec2.end() );              uint128 e5 = power5( e );             int i = 0, j = (int)vec2.size()-1, mx_i = (int)vec1.size();             while( i < mx_i && j >= 0 )             {                 while ( j >= 0 && vec1[i].first + vec2[j].first > e5 ) j--;                 if ( j >= 0 && vec1[i].first + vec2[j].first == e5 )                 {                     int a = vec1[i].second.first;                     int b = vec1[i].second.second;                     int c = vec2[j].second.first;                     int d = vec2[j].second.second;                     if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                         printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }                 i++;             }         }          \/\/ (e^5 - a^5) - (b^5 + c^5) = d^5         \/\/ (b^5 + c^5) = w  (mod p)         \/\/ already computed as vec1         for (int d=11; d<=n; d+=11)         {             \/\/ (e^5 - a^5) = (d^5 + w) = q  (mod p)             uint64 d5p = ((uint64)d*d)%p;             d5p = ((d5p*d5p)%p*d)%p;             int q = (int)((d5p + w)%p);             vector< pair< uint128, pair< int, int > > > vec2;              for (int e=1; e<=n; e++)             {                 uint64 e5p = ((uint64)e*e)%p;                 e5p = ((e5p*e5p)%p*e)%p;                 int a = sols[ (e5p - q + p)%p ];                 if (a!=-1 && a<e)                 {                     uint128 e5 = power5( e );                     uint128 a5 = power5( a );                     int E = e%11, E5 = (E*E*E*E*E)%11;                     int A = a%11, A5 = (A*A*A*A*A)%11;                     if ( (E5-A5+11)%11 == 0 )                         vec2.push_back( make_pair( e5-a5, make_pair( e, a ) ) );                 }             }              sort( vec2.begin(), vec2.end() );              uint128 d5 = power5( d );             int i = 0, j = 0, mx_i = (int)vec2.size(), mx_j = (int)vec1.size();             while (i < mx_i && j < mx_j)             {                 while (j < mx_j && vec2[i].first > vec1[j].first && vec2[i].first - vec1[j].first > d5) j++;                 if ( j < mx_j && vec2[i].first > vec1[j].first && vec2[i].first - vec1[j].first == d5 )                 {                     int e = vec2[i].second.first;                     int a = vec2[i].second.second;                     int b = vec1[j].second.first;                     int c = vec1[j].second.second;                     if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                         printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }                 i++;             }         }     } } <\/code><\/pre>\n
      <\/div>\n<\/div>\n
      \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u044d\u0442\u0443 \u0436\u0435\u0441\u0442\u043e\u043a\u0443\u044e \u0436\u0435\u0441\u0442\u044c:  <\/p>\n\n\n\n\n\n\n\n\n\n
    n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n#6<\/th>\n#7<\/th>\n#8<\/th>\n#9<\/th>\n<\/tr>\n
    100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n129ms<\/td>\n20ms<\/td>\n16ms<\/td>\n219ms<\/td>\n<\/tr>\n
    200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n140ms<\/td>\n105ms<\/td>\n49ms<\/td>\n1741ms<\/td>\n<\/tr>\n
    500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n375ms<\/td>\n1014ms<\/td>\n472ms<\/td>\n25s<\/td>\n<\/tr>\n
    1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n2559ms<\/td>\n7096ms<\/td>\n2110ms<\/td>\n200s<\/td>\n<\/tr>\n
    2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n38s<\/td>\n52s<\/td>\n13s<\/td>\n28m<\/td>\n<\/tr>\n
    5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n28m<\/td>\n13m<\/td>\n161s<\/td>\n<\/td>\n<\/tr>\n
    10000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n89m<\/td>\n20m<\/td>\n<\/td>\n<\/tr>\n<\/table>\n
      \u0413\u043e\u0441\u043f\u043e\u0434\u0430, \u0434\u043e\u0431\u0440\u043e \u043f\u043e\u0436\u0430\u043b\u043e\u0432\u0430\u0442\u044c \u0441\u043d\u043e\u0432\u0430 \u0432 \u043a\u0430\u043c\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a! \u0427\u0442\u043e \u0436 \u043e\u043d\u043e \u0442\u0430\u043a \u0442\u043e\u0440\u043c\u043e\u0437\u0438\u0442-\u0442\u043e \u0431\u0435\u0437\u0431\u043e\u0436\u043d\u043e? \u0410\u0445 \u0434\u0430, \u0442\u0430\u043c \u0436\u0435 \u0442\u0435\u043f\u0435\u0440\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044f power5() \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u043d\u0435 \u0442\u0440\u0435\u0445 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0446\u0438\u043a\u043b\u043e\u0432, \u0432\u043d\u0443\u0442\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0446\u0438\u043a\u043b \u0430\u0436 \u043d\u0430 63 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438. \u041f\u0435\u0440\u0435\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u043d\u0430 \u0438\u043d\u0442\u0440\u0438\u043d\u0441\u0438\u043a\u0438? \u0421\u043f\u043e\u043a\u043e\u0439\u043d\u043e, \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u0443\u0434\u0435\u043c \u0442\u0430\u0449\u0438\u0442\u044c \u043e\u0442\u0432\u0435\u0442 \u0438\u0437 \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043d\u043d\u043e\u0439 \u0442\u0430\u0431\u043b\u0438\u0447\u043a\u0438.<\/p>\n
      \u0417\u0430\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043e\u043d\u043e \u043f\u043e\u0447\u0442\u0438 \u043d\u0435 \u0435\u0441\u0442 \u043f\u0430\u043c\u044f\u0442\u044c, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u043e\u0434\u043d\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e: \u0442\u0435\u043f\u0435\u0440\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u043d\u0430 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0435 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u043e \u0435\u0441\u0442\u044c \u00ab\u0440\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0442\u044c\u00bb, \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 \u2014 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044f\u0434\u0435\u0440. \u0410 \u0438\u043c\u0435\u043d\u043d\u043e: \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044f\u0434\u0440\u0430 \u0434\u0430\u0432\u0430\u0442\u044c \u0441\u0432\u043e\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 w \u0438 \u043f\u0440\u0438 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0438 \u044d\u0442\u0438\u043c\u0438 w \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 0 \u0434\u043e p-1 \u043c\u044b \u043f\u043e\u043a\u0440\u043e\u0435\u043c \u0432\u0441\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u0432 \u0437\u0430\u0434\u0430\u0447\u0435, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0430\u0433\u0440\u0443\u0437\u043a\u0430 \u043d\u0430 \u0432\u0441\u0435 \u044f\u0434\u0440\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u043e.<\/p>\n
      \u041f\u043b\u044e\u0441\u044b: \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u044f\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f.
      \u041c\u0438\u043d\u0443\u0441\u044b: \u0442\u043e\u0440\u043c\u043e\u0437\u0438\u0442 \u043a\u0430\u043a \u0441\u0430\u043f\u043e\u0436\u043d\u0438\u043a \u0441 \u043f\u043e\u0445\u043c\u0435\u043b\u044c\u044f.<\/p>\n
    \u0421\u043a\u0430\u0437\u043a\u0430 #10 \u0437\u0430 O(n3<\/sup>log n) \u0441 \u0445\u0430\u0440\u0434\u043a\u043e\u0440\u043d\u044b\u043c\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438<\/h1>\n
      \u0411\u0435\u0440\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 #9 \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0445\u0430\u0440\u0434\u043a\u043e\u0440\u043d\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u041d\u0443, \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043d\u0435 \u0442\u0430\u043a\u0438\u0435 \u0443\u0436 \u043e\u043d\u0438 \u0438 \u0445\u0430\u0440\u0434\u043a\u043e\u0440\u043d\u044b\u0435. \u041d\u043e \u0438\u0445 \u043c\u043d\u043e\u0433\u043e:  <\/p>\n
      \n
    • \u041f\u0440\u0435\u0434\u043f\u0440\u043e\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0435, \u0447\u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0438 \u0432\u044b\u043d\u043e\u0441\u0438\u043c \u0432 \u0442\u0430\u0431\u043b\u0438\u0447\u043a\u0438.<\/li>\n
    • \u041e\u0442\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0441\u044f \u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0441 \u0438\u0445 push_back-\u0430\u043c\u0438 \u0438 \u043f\u0435\u0440\u0435\u0434\u0435\u043b\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0435 \u043d\u0430 \u0441\u0442\u0430\u0442\u0438\u0447\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b.<\/li>\n
    • \u0412\u0435\u0437\u0434\u0435, \u0433\u0434\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043c\u043e\u0436\u043d\u043e, \u0443\u0431\u0438\u0440\u0430\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u0437\u044f\u0442\u0438\u044f \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f.<\/li>\n
    • \u0412 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445 \u0434\u043b\u044f \u043f\u0430\u0440 \u0442\u0435\u043f\u0435\u0440\u044c \u0445\u0440\u0430\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0443\u043c\u043c\u0443 (\u0438\u043b\u0438 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c) \u043f\u044f\u0442\u044b\u0445 \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439, \u0430 \u0441\u0430\u043c\u0438 \u043f\u0430\u0440\u044b \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0442\u0430\u043a \u043a\u0430\u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0434\u043a\u0438 \u2014 \u043f\u0430\u0440\u0430 \u0438\u0449\u0435\u0442\u0441\u044f \u0432\u0442\u0443\u043f\u0443\u044e \u0437\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442).<\/li>\n
    • \u041c\u0430\u0441\u0441\u0438\u0432\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0432\u043d\u0443\u0442\u0440\u0438 \u0446\u0438\u043a\u043b\u043e\u0432 \u043f\u043e e \u0438 d \u0442\u0435\u043f\u0435\u0440\u044c \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0432 2 \u0440\u0430\u0437\u0430 \u043a\u043e\u0440\u043e\u0447\u0435. \u0414\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0434\u043b\u044f \u0441\u043b\u0443\u0447\u0430\u044f (a5<\/sup> + b5<\/sup>) + (c5<\/sup> + d5<\/sup>) = e5<\/sup> \u043d\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e (c5<\/sup> + d5<\/sup>) < e5<\/sup> (\u0445\u043e\u0440\u043e\u0448\u043e \u043f\u0440\u0438 \u043c\u0430\u043b\u044b\u0445 e), \u0430 \u0434\u043b\u044f (e5<\/sup> \u2014 a5<\/sup>) \u2014 (b5<\/sup> + c5<\/sup>) = d5<\/sup> \u043d\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e (e5<\/sup> \u2014 a5<\/sup>) > d5<\/sup> (\u0445\u043e\u0440\u043e\u0448\u043e \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 d).<\/li>\n<\/ul>\n
        \u0418 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043a\u043e\u0434:  <\/p>\n
      \u041a\u043e\u0434<\/b><\/p>\n
      \n
      #define MAXN 100500  int pow5modp[MAXN]; int sols[MAXN]; uint128 vec1[MAXN], vec2[MAXN]; int vec1_sz, vec2_sz; uint128 pow5[MAXN]; int pow5mod11[MAXN];  void init_arrays( int n, int p ) {     for (int i=1; i<=n; i++)     {         uint64 i5p = ((uint64)i*i)%p;         i5p = (((i5p*i5p)%p)*i)%p;         pow5modp[i] = (int)i5p;     }      for (int i=0; i<p; i++)         sols[i] = -1;     for (int i=1; i<=n; i++)         sols[pow5modp[i]] = i;      for (int i=1; i<=n; i++)         pow5[i] = power5(i);      for (int i=1; i<=n; i++)     {         int ii = i%11;         pow5mod11[i] = (ii*ii*ii*ii*ii)%11;     } }  void tale10( int n, int start=0, int step=1 ) {     int p = n+1;     while ( p%5==1 || !is_prime( p ) ) p++;      init_arrays( n, p );\t      for (int w=start; w<p; w+=step)     {         cerr << "n=" << n << " p=" << p << " w=" << w << "\\n";         \/\/ (a^5 + b^5) + (c^5 + d^5) = e^5         \/\/ (a^5 + b^5) = w  (mod p)         vec1_sz = 0;         for (int a=1; a<=n; a++)         {             int tmp = w - pow5modp[a];             int b = sols[ tmp<0 ? tmp+p : tmp ];             if (b!=-1 && b<a)                 if ( (pow5mod11[a]+pow5mod11[b])%11 == 0 )                     vec1[vec1_sz++] = pow5[a]+pow5[b];         }          sort( vec1, vec1 + vec1_sz );          for (int e=11; e<=n; e+=11)         {             \/\/ (a^5 + b^5) + (c^5 + d^5) = e^5             \/\/ (a^5 + b^5) = w  (mod p)             \/\/ (c^5 + d^5) = (e^5 - w) = q  (mod p)             int q = (int)((pow5modp[e] - w + p)%p);             uint128 e5 = pow5[e];             vec2_sz = 0;              for (int c=1; c<e; c++)             {                 int tmp = q - pow5modp[c];                 int d = sols[ tmp<0 ? tmp+p : tmp ];                 if (d!=-1 && d<c)                     if ( pow5mod11[c]+pow5mod11[d]==0 || pow5mod11[c]+pow5mod11[d]==11 )                     {                         uint128 s = pow5[c]+pow5[d];                         if (s < e5) vec2[vec2_sz++] = s;                     }             }              sort( vec2, vec2 + vec2_sz );              int i = 0, j = vec2_sz-1, mx_i = vec1_sz-1;             while( i < mx_i && j >= 0 )             {                 while ( j >= 0 && vec1[i] + vec2[j] > e5 ) j--;                 if ( j >= 0 && vec1[i] + vec2[j] == e5 )                 {                     int a=-1, b=-1, c=-1, d=-1;                     for (int A=1; A<=n; A++)                         for (int B=1; B<A; B++)                             if (pow5[A]+pow5[B]==vec1[i])                             {                                 a=A;                                 b=B;                             }                     for (int C=1; C<=n; C++)                         for (int D=1; D<C; D++)                             if (pow5[C]+pow5[D]==vec2[j])                             {                                 c=C;                                 d=D;                             }                     if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                         printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }                 i++;             }         }          \/\/ (e^5 - a^5) - (b^5 + c^5) = d^5         \/\/ (b^5 + c^5) = w  (mod p)         \/\/ already computed as vec1         for (int d=11; d<=n; d+=11)         {             \/\/ (e^5 - a^5) = (d^5 + w) = q  (mod p)             int q = (int)((pow5modp[d] + w)%p);             uint128 d5 = pow5[d];             vec2_sz = 0;              for (int e=d+1; e<=n; e++)             {                 int tmp = pow5modp[e]-q;                 int a = sols[ tmp<0 ? tmp+p : tmp ];                 if (a!=-1 && a<e)                     if ( pow5mod11[e]==pow5mod11[a] )                     {                         uint128 s = pow5[e]-pow5[a];                         if (s > d5) vec2[vec2_sz++] = s;                     }             }              sort( vec2, vec2 + vec2_sz );              int i = 0, j = 0, mx_i = vec2_sz, mx_j = vec1_sz;             while (i < mx_i && j < mx_j)             {                 while (j < mx_j && vec2[i] > vec1[j] && vec2[i] - vec1[j] > d5) j++;                 if ( j < mx_j && vec2[i] > vec1[j] && vec2[i] - vec1[j] == d5 )                 {                     int e=-1, a=-1, b=-1, c=-1;                     for (int E=1; E<=n; E++)                         for (int A=1; A<E; A++)                             if (pow5[E]-pow5[A]==vec2[i])                             {                                 e = E;                                 a = A;                             }                     for (int B=1; B<=n; B++)                         for (int C=1; C<B; C++)                             if (pow5[B]+pow5[C]==vec1[j])                             {                                 b = B;                                 c = B;                             }                     if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1)                         printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\\n", a, b, c, d, e );                 }                 i++;             }         }     } } <\/code><\/pre>\n
        <\/div>\n<\/div>\n
        \u041a\u043e\u0434 \u0441\u0442\u0430\u043b \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u0435\u0435, \u043f\u0440\u043e\u0449\u0435 \u0438 \u0434\u043e\u0431\u0440\u0435\u0435, \u0447\u0442\u043e \u043b\u0438. \u0410 \u0435\u0449\u0435 \u043e\u043d \u0441\u0442\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u0435\u0435:  <\/p>\n\n\n\n\n\n\n\n\n\n
      n<\/th>\n#1<\/th>\n#2<\/th>\n#3<\/th>\n#4<\/th>\n#5<\/th>\n#6<\/th>\n#7<\/th>\n#8<\/th>\n#9<\/th>\n#10<\/th>\n<\/tr>\n
      100<\/td>\n1563ms<\/td>\n318ms<\/td>\n490ms<\/td>\n360ms<\/td>\n82ms<\/td>\n129ms<\/td>\n20ms<\/td>\n16ms<\/td>\n219ms<\/td>\n8ms<\/td>\n<\/tr>\n
      200<\/td>\n40s<\/td>\n4140ms<\/td>\n6728ms<\/td>\n4339ms<\/td>\n121ms<\/td>\n140ms<\/td>\n105ms<\/td>\n49ms<\/td>\n1741ms<\/td>\n30ms<\/td>\n<\/tr>\n
      500<\/td>\n74m<\/td>\n189s<\/td>\n352s<\/td>\n177s<\/td>\n516ms<\/td>\n375ms<\/td>\n1014ms<\/td>\n472ms<\/td>\n25s<\/td>\n379ms<\/td>\n<\/tr>\n
      1000<\/td>\n<\/td>\n55m<\/td>\n<\/td>\n46m<\/td>\n3119ms<\/td>\n2559ms<\/td>\n7096ms<\/td>\n2110ms<\/td>\n200s<\/td>\n2993ms<\/td>\n<\/tr>\n
      2000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n22s<\/td>\n38s<\/td>\n52s<\/td>\n13s<\/td>\n28m<\/td>\n24s<\/td>\n<\/tr>\n
      5000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n328s<\/td>\n28m<\/td>\n13m<\/td>\n161s<\/td>\n<\/td>\n405s<\/td>\n<\/tr>\n
      10000<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n89m<\/td>\n20m<\/td>\n<\/td>\n59m<\/td>\n<\/tr>\n<\/table>\n
        \u041c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043b\u0438 \u0432\u0441\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0434\u043b\u044f n=10000 \u0437\u0430 \u0431\u043e\u043b\u0435\u0435-\u043c\u0435\u043d\u0435\u0435 \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0436\u0430\u043b\u043a\u0438\u0435 10 \u041c\u0431 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n
        \u041f\u043b\u044e\u0441\u044b: \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0435, \u0435\u0441\u0442 \u043c\u0430\u043b\u043e \u043f\u0430\u043c\u044f\u0442\u0438.
        \u041c\u0438\u043d\u0443\u0441\u044b: \u0438\u0445 \u043d\u0435\u0442.<\/p>\n
      \u041d\u0438 \u0432 \u0441\u043a\u0430\u0437\u043a\u0435 \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u043d\u0438 \u043f\u0435\u0440\u043e\u043c \u043e\u043f\u0438\u0441\u0430\u0442\u044c<\/h1>\n
        \u0410 \u0422\u0415\u041f\u0415\u0420\u042c \u044f \u0434\u043e\u0441\u0442\u0430\u044e \u0438\u0437 \u0448\u0438\u0440\u043e\u043a\u0438\u0445 \u0448\u0442\u0430\u043d\u0438\u043d 64-\u0431\u0438\u0442\u043d\u044b\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440, 6-\u044f\u0434\u0435\u0440\u043d\u044b\u0439 i7-5820K 3.3GHz \u0438 4-\u044f\u0434\u0435\u0440\u043d\u044b\u0439 i7-3770 3.4GHz \u0438 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u044e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 #10 \u0432 16 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u043d\u0435\u0439.  <\/p>\n\n\n\n\n\n\n
      n<\/th>\n\u0421\u0443\u043c\u043c\u0430\u0440\u043d\u043e \u043f\u043e \u044f\u0434\u0440\u0430\u043c<\/th>\n\u0420\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/th>\n\u041f\u043e\u0442\u043e\u043a\u043e\u0432<\/th>\n<\/tr>\n
      10000<\/td>\n29m<\/td>\n29m<\/td>\n1<\/td>\n<\/tr>\n
      20000<\/td>\n318m<\/td>\n58m<\/td>\n6<\/td>\n<\/tr>\n
      50000<\/td>\n105h<\/td>\n7h<\/td>\n16<\/td>\n<\/tr>\n
      100000<\/td>\n\u043e\u0436\u0438\u0434\u0430\u0435\u0442\u0441\u044f ~960h (80% done*)<\/td>\n\u043e\u0436\u0438\u0434\u0430\u0435\u0442\u0441\u044f ~60h (80% done*)<\/td>\n16<\/td>\n<\/tr>\n<\/table>\n
        * \u043f\u0440\u043e\u0448\u0443 \u043c\u0435\u043d\u044f \u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c \u0437\u0430 \u043c\u043e\u0435 \u043d\u0435\u0442\u0435\u0440\u043f\u0435\u043d\u0438\u0435, \u044f \u043d\u0430\u043f\u0438\u0448\u0443 \u0442\u043e\u0447\u043d\u044b\u0435 \u0446\u0438\u0444\u0440\u044b \u043a\u043e\u0433\u0434\u0430 \u043e\u043d\u043e \u0434\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u0442.<\/p>\n
        64-\u0431\u0438\u0442\u043d\u0430\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u0435 (\u043d\u0430\u043f\u043e\u043c\u043d\u044e, \u0440\u0430\u043d\u0435\u0435 \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u043a\u043e\u0434 \u043d\u0430 i5-2410M 2.3Ghz) \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0432 2 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u0412 \u0438\u0442\u043e\u0433\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0437\u0430\u0442\u0430\u0449\u0438\u0442\u044c n=100000 \u0438 \u043d\u0430\u0439\u0442\u0438** \u0432\u0442\u043e\u0440\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u0434\u0438\u043e\u0444\u0430\u043d\u0442\u043e\u0432\u0430 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n
        555<\/sup> + 31835<\/sup> + 289695<\/sup> + 852825<\/sup> = 853595<\/sup><\/p>\n
        ** \u041f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043d\u0430\u0447\u0430\u0442\u044c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0447\u0435\u0442\u044b, \u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043b \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e w \u043e\u0442\u0432\u0435\u0442 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d, \u043f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043b \u0435\u0433\u043e \u2014 \u0438 \u0432\u0441\u0435 \u0441\u043e\u0448\u043b\u043e\u0441\u044c.<\/p>\n
      \u0421\u043a\u0430\u0437\u043a\u0430 \u2014 \u043b\u043e\u0436\u044c, \u0434\u0430 \u0432 \u043d\u0435\u0439 \u043d\u0430\u043c\u0435\u043a<\/h1>\n
        \u0412\u043e\u0442 \u0442\u0430\u043a \u0432\u043e\u0442 \u043d\u0435 \u0441\u0430\u043c\u043e\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043d\u0435 \u0441\u0430\u043c\u043e\u0439 \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u043e\u0439 \u0431\u044b\u0432\u0430\u0435\u0442 \u043b\u0443\u0447\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435.<\/p>\n
        \u041f\u043e \u0438\u0434\u0435\u0435, \u043a\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0435\u0449\u0435 \u0438\u043b\u0438 \u043e\u0442\u0440\u0435\u0437\u0430\u0442\u044c \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u043e\u0442 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0438, \u043d\u043e \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043c\u043d\u0435 \u043f\u043e\u043a\u0430 \u043d\u0430\u0434\u043e\u0435\u043b\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u2014 \u044f \u0443\u0436\u0435 \u043f\u043e\u0442\u0435\u0440\u044f\u043b \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/i>. \u041d\u0430\u0441\u0447\u0435\u0442 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0432\u0430: \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043d\u0430 radix sort (\u043d\u043e \u0442\u043e\u0433\u0434\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0435\u0442 \u0434\u043e \u043a\u043e\u0441\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432), \u043b\u0438\u0431\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u0438\u0434\u0435\u0438 \u0434\u0432\u0443\u0445 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0443 (\u0442\u0443\u0442 \u0443\u0436\u0435 \u043d\u0430\u0434\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0438 \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0447\u0442\u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435). \u041f\u0440\u043e\u0444\u0438\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0430, \u0447\u0442\u043e \u0434\u043b\u044f n=10000 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u0432\u0441\u0435\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 n \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0442\u0435\u0440\u043f\u0438\u043c\u044b\u0439. \u041d\u0430\u0441\u0447\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f: \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0435\u0441\u0442\u044c \u0435\u0449\u0435 \u043a\u0430\u043a\u0438\u0435-\u043d\u0438\u0431\u0443\u0434\u044c \u0442\u0440\u044e\u043a\u0438 \u0441 \u043c\u043e\u0434\u0443\u043b\u044f\u043c\u0438, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0432 5-10 \u0440\u0430\u0437.<\/p>\n
      \u0417\u0430\u0442\u0430\u0449\u0438\u043c?<\/h1>\n
        \u0415\u0449\u0435 \u0443 \u043c\u0435\u043d\u044f \u0435\u0441\u0442\u044c \u0434\u0438\u043a\u0430\u044f \u0438\u0434\u0435\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0432\u0441\u0435 n \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430. \u041e\u0436\u0438\u0434\u0430\u0435\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438, \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435, \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0435 \u2014 \u043e\u043a\u043e\u043b\u043e \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u044f\u0434\u0440\u043e\u0447\u0430\u0441\u043e\u0432. \u041d\u043e \u043c\u043e\u0438\u0445 \u043c\u043e\u0449\u043d\u043e\u0441\u0442\u0435\u0439 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u044f\u0432\u043d\u043e \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u0417\u0430\u0442\u0430\u0449\u0438\u043c \u0432\u043c\u0435\u0441\u0442\u0435? \u0412\u043f\u0440\u043e\u0447\u0435\u043c, \u044f \u043d\u0435 \u043d\u0430\u0448\u0435\u043b \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0442\u043e\u043c, \u0434\u043e \u043a\u0430\u043a\u043e\u0433\u043e n \u0443\u0436\u0435 \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u043b\u0438. \u041c\u043e\u0436\u0435\u0442 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u0438\u0441\u043a\u0430\u0442\u044c \u0443\u0436\u0435 \u043d\u0435\u0442 \u0441\u043c\u044b\u0441\u043b\u0430, \u0438\u0431\u043e \u0432\u0441\u0435 \u0434\u0430\u0432\u043d\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043d\u043e. \u041f\u0440\u043e\u0448\u0443 \u043e\u0442\u043f\u0438\u0441\u0430\u0442\u044c\u0441\u044f, \u0435\u0441\u043b\u0438 \u0443 \u043a\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u043f\u043e\u0432\u043e\u0434\u0443.<\/p>\n
      \u0422\u0443\u0442 \u0438 \u0441\u043a\u0430\u0437\u043e\u0447\u043a\u0435 \u043a\u043e\u043d\u0435\u0446, \u043a\u0442\u043e \u043e\u0441\u0438\u043b\u0438\u043b \u2014 \u043c\u043e\u043b\u043e\u0434\u0435\u0446!<\/h3>\n
       \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habrahabr.ru\/post\/318244\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
      \u041f\u0440\u0438\u0432\u0435\u0442 \u0425\u0430\u0431\u0440!<\/p>\n
        \u042f \u0440\u0435\u0448\u0438\u043b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u0441\u0435\u0440\u0438\u044e<\/a> \u0441\u0442\u0430\u0442\u0435\u0439<\/a> \u043f\u0440\u043e \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0443 \u042d\u0439\u043b\u0435\u0440\u0430, \u043d\u0430\u043f\u0438\u0441\u0430\u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0438\u043e\u0444\u0430\u043d\u0442\u043e\u0432\u0430 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0432\u0438\u0434\u0430 a5<\/sup> + b5<\/sup> + c5<\/sup> + d5<\/sup> = e5<\/sup>.<\/p>\n
      <\/div>\n
        \u041a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u043a\u0430\u043a\u0443\u044e-\u043b\u0438\u0431\u043e \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043f\u0443\u043d\u043a\u0442\u044b:  <\/p>\n
        \n
      1. \u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/li>\n
      2. \u0411\u044b\u0441\u0442\u0440\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/li>\n
      3. \u041c\u043e\u0449\u043d\u043e\u0435 \u0436\u0435\u043b\u0435\u0437\u043e<\/li>\n
      4. \u0420\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0432\u0430\u043d\u0438\u0435<\/li>\n<\/ol>\n
          \u042f \u0443\u0434\u0435\u043b\u0438\u043b \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u043f\u0443\u043d\u043a\u0442\u0443. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u0447\u0442\u043e \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-283083","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/283083","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=283083"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/283083\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=283083"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=283083"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=283083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}