Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. program cat5;
  2. {$OVERFLOWCHECKS ON}
  3.     var
  4.            a,b,s,s1,s2:QWORD;
  5.            i:integer;
  6.  
  7.     function root(x: qword; y: integer): Int64;
  8.       var
  9.         k,h,d : qword;
  10.         m,l,r : qword;
  11.         j:integer;
  12.         over:boolean;
  13.       begin
  14.         l:=1;
  15.         r:=x;
  16.         while (r-l>1) do
  17.           begin //Сейчас попробую расписать объяснение задачи
  18.             m:=l+((r-l)div 2);
  19.             j:=y;// В принципе задача не сложное по сути это выделение корня n-ной степени
  20.             k:=m; //И единственная сложность это поимка переполнения
  21.             h:=1; //Буду писать объяснения слегка хаотично, пл этому буду ставить цифры по порядку как читать
  22.             over:=false;
  23.                 while (j<>0)   do
  24.                 begin
  25.                   if (j mod 2 = 1) then
  26.                       begin
  27.                         // Часть 2
  28.                         d:= high(qword) div k;  // Тут мы делаем такую же проверку как и в первом случае, за одним исключением
  29.                         //Чем Ближе наша середина М будет приближаться к корню из большого числа а тем больше свою роль будет играть погрешность целочисленного деление
  30.                         if ( high(qword) mod k > 0) then d:=d+1;//Для того чтобы это избежать, мы делаем проверку на остаток при делении
  31.                         if ( d > h) then h:=h*k else// если остаток есть мы условно увеличиваем наше число D, что является отношением  Qword а и К, на 1
  32.                           begin// дальше мы сравниваем  D b H и если D оказалось больше то мы делаем обычное умножение
  33.                             over:=true; // Иначе говорим что переполнение произошло и выходим их цикла
  34.                             break;
  35.                           end;
  36.                       end;
  37.                   //Часть 1
  38.                       if (high(qword) div k > k) then k:=k*k else k:=(high(qword));
  39.                       j:=j div 2; // Первое выше написана проверка на переполнение делением Qword а на множитель К
  40.                 end;// если если полученное при деление число больше К то мы можем выполнять умножение
  41.                 //иначе произошло переполнение и мы К приравниваем к Qword у
  42.  
  43.  
  44.              // Часть 3
  45.             if (over) then r:=m   //  Если произошло переполнение, то мы просто сдвигаем правую границу
  46.             //так как мы прекрасно понимаем что если произошло переполнение, то число которое мы ищем 100% меньше этого числа М
  47.               else   // Иначе проходим обычную проверку бинарного поиска
  48.                 begin
  49.                   if (h>x) then r:=m else l:=m;
  50.                 end;
  51.             end;
  52.         root:=l;
  53.       end;
  54.  
  55.  
  56.       begin
  57.         assign (input,'input.txt');reset(input);
  58.         assign (output,'output.txt');rewrite(output);
  59.         read (a,b);
  60.         s:=0;
  61.         i:=2;
  62.         s1:=0;
  63.         s2:=0;
  64.  
  65.           while (i<65) do
  66.             begin
  67.               s2:=root (b,i);
  68.               s1:=root (a-1,i);
  69.               s:=s+(s2-s1);
  70.               i:=i+1;
  71.             end;
  72.  
  73.         write (s);
  74.  
  75.         close(output);
  76.       end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement