Editorial for Whirligig number


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var p:array[1..50] of int64;
    a,b,re:int64;

procedure rf;
begin
     read(a,b);
end;

procedure init;
var i:longint; j:int64;
begin
     p[1]:=2;
     for i:=2 to 50 do p[i]:=p[i-1]*2;
end;

procedure pr;
var i:longint; m,n,lnum,num:int64;
begin
     init;
     re:=0; lnum:=0; num:=0;
     for i:=50 downto 1 do
     begin
          if a mod p[i] <> 0 then m:=a+p[i]-a mod p[i]
          else m:=a;
          n:=b-b mod p[i];
          if n>=m then
          begin
               num:=(n-m) div p[i] + 1;
               re:=re+(num-lnum)*p[i];
               lnum:=num;
          end;
     end;
     re:=re+(b-a+1-num);
end;

procedure wf;
begin
     write(re);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>

int main() {
    long long a, b, res = 0;
    scanf("%lld%lld", &a, &b); --a;
    for(int i = 0; b >> i; ++i) {
        res += (b >> i+1) + (b >> i & 1) << i;
        res -= (a >> i+1) + (a >> i & 1) << i;
    }
    printf("%lld\n", res);
    return 0;
}

Code mẫu của ladpro98

program mzvrk;
uses    math;
var     a,b:int64;
        res,pow:int64;
        i:longint;
        f:array[0..50] of int64;
function q(k:int64):int64;
begin
        exit(b div k - (a-1) div k);
end;
begin
        readln(a,b);
        res:=(b+1) shr 1;
        if a>1 then res:=res-a shr 1;
        pow:=2;
        f[0]:=q(2);
        for i:=1 to 50 do
        begin
                f[i]:=q(pow);
                dec(f[i-1],f[i]);
                res:=res+f[i-1]*(pow shr 1);
                pow:=pow shl 1;
                if f[i]=0 then break
        end;
        write(res);
end.

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
var
  f1,f2:text;
  a,b:int64;
  lt2:array[0..50] of int64;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure init;
var
  i:longint;
begin
  lt2[0]:=1;
  for i:=1 to 50 do lt2[i]:=lt2[i-1]<<1;
end;
function cal(a:int64):int64;
var
  ii,i:longint;
  sum,now,dx:int64;
begin
  for i:=0 to 50 do
    if lt2[i]>a then
      begin
        ii:=i;
        break;
      end;
  dx:=0; sum:=0;
  for i:=ii downto 0 do
    begin
      now:=a div lt2[i]-dx;
      sum+=lt2[i]*now;
      dx+=now;
    end;
  exit(sum);
end;
begin
  openF;
  init;
  readln(f1,a,b);
  writeln(f2,cal(b)-cal(a-1));
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
long long f(long long N)
{
if(N==0)
  return 0;
else if(N==1)
  return 1;  
else
{       
long long T=N,t=0;
do
  {
  N=N/2;
  T=T+N*pow(2,t);
  t++;
  }while(N!=1);
return T;
}
}                
main()
{
long long a,b;
scanf("%lld %lld",&a,&b);
printf("%lld",f(b)-f(a-1));
//getch();
}

Code mẫu của ll931110

Program MZVRK;
        Var
                a,b: int64;
                res: qword;

Procedure solve;
          Var
                i,k,tmp: int64;
          Begin
                res:= b - (a - 1);
                i:= 1;
                k:= 1;

                While i <= a - 1 do
                        Begin
                                i:= i * 2;
                                If i <= a - 1 then
                                        Begin
                                                tmp:= b div i;
                                                tmp:= tmp - (a - 1) div i;

                                                res:= res + tmp * k;
                                                k:= k * 2;
                                        End;
                        End;

                i:= i div 2;
                If i = 0 then i:= 1;

                While i <= b do
                        Begin
                                i:= i * 2;

                                If i <= b then
                                        Begin
                                                tmp:= b div i;
                                                res:= res + tmp * k;
                                                k:= k * 2;
                                        End;
                        End;
          End;

Begin
        Readln(a,b);
        solve;
        Writeln(res);
        Readln;
End.

Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE}
 {$mode delphi}

var
    res, z, a, b : int64;
    c, f : array[0..50] of int64;
    i, j : integer;
begin
    read(a,b);
    z := 1;
    res := 0;
    for i:=0 to 50 do
    begin
        c[i] := z;
        f[i] := b div z - (a-1) div z;
        z := z * 2;
    end;
    for i:=50 downto 1 do
        for j:=i-1 downto 0 do
            f[j] := f[j] - f[i];
    for i:=0 to 50 do res := res + c[i] * f[i];
    writeln(res);
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.