首页 > 代码库 > 【数论Day3】进制问题 题解

【数论Day3】进制问题 题解

数论进入第三天,进制问题是常用提醒,是数论的一个重要知识点,常考!

题面:http://www.cnblogs.com/ljc20020730/p/6935255.html

1.K进制数(Kbased.pas/c/cpp)

首先明确数据范围:

【数据规模和约定】

  对于40%的数据,a的长度不超过5。

  对于100%的数据,a的长度不超过100000。

对于40%暴力枚举不多说,上代码:

var t,i,k,tt:longint;
    a:qword;
    s:string;
function pow(x,n:qword):qword;
begin
  if n=0 then exit(1);
  pow:=pow(x,n>>1);
  pow:=pow*pow;
  if n mod 2=1 then pow:=(pow*x);
end;
function f(s:string):qword;
var tx,i:longint;
    w:array[0..5]of longint;
    x:qword;
begin
 fillchar(w,sizeof(w),0);
 w[0]:=length(s);
 for i:=1 to length(s) do begin
  if (s[i]<=9)and(s[i]>=0) then
  w[i]:=ord(s[i])-ord(0)
  else w[i]:=ord(s[i])-ord(A)+10;
 end;
 x:=0;
 tx:=w[0]-1;
 for i:=1 to w[0] do begin
 x:=x+pow(k,tx)*w[i]; dec(tx); end;
 exit(x);
end;
begin
assign(input,kbased.in);
assign(output,kbased.out);
reset(input);
rewrite(output);
 readln(t);
 for i:=1 to t do begin
  readln(k);
  readln(s);
  a:=f(s);
  if a mod (k-1)=0 then writeln(yes)
  else writeln(no);
 end;
end.

40分非常妥!
但是:对于100%的数据,a的长度不超过100000。
怎么处理?
思考一个问题:每一个k进制数可以表示为什么? 

任何一个k进制正整数都可以写成:a0*k0+a1*k1+…+an*kn

这是初赛的内容吧,相信来看题解的人这点心中自然明确。

对于几乎要达到线性的时间复杂度来说,必须要从Kn这里下手!

那么来看一个非常简单的例子:

∵k0=1∴ k0 mod (k-1) = 1

∵k1=k-1+1∴ k1 mod (k-1) = 1

∵k2 = k*k∴ k2 mod (k-1) = 1

……

所以推出:kn = kn-1*kkn mod (k-1) = 1

没问题吧?

●任何一个k进制正整数都可以写成:a0*k0+a1*k1+…+an*kn

又因为所有的k?k-1都是1(?是一个常数)

所以任何一个k进制正整数,模k-1的结果,都等于它各个数位上数字之和模k-1

任何一个k进制正整数都可以写成:a0*k0+a1*k1+…+an*kn

这是初赛的内容吧,相信来看题解的人这点心中自然明确。

对于几乎要达到线性的时间复杂度来说,必须要从Kn这里下手!

那么来看一个非常简单的例子:

∵k0=1∴ k0 mod (k-1) = 1

∵k1=k-1+1∴ k1 mod (k-1) = 1

∵k2 = k*k∴ k2 mod (k-1) = 1

……

所以推出:kn = kn-1*kkn mod (k-1) = 1

没问题吧?

●任何一个k进制正整数都可以写成:a0*k0+a1*k1+…+an*kn

又因为所有的k?k-1都是1(?是一个常数)

所以任何一个k进制正整数,模k-1的结果,都等于它各个数位上数字之和模k-1

【程序】

var  w:array[0..100000]of longint;
     t,i,k:longint;
     s:ansistring;
     a:qword;
function f(s:ansistring):qword;
var i:longint;
    ans:qword;
begin
 fillchar(w,sizeof(w),0);
 w[0]:=length(s);
 ans:=0;
 for i:=1 to length(s) do begin
  if (s[i]<=9)and(s[i]>=0) then
  w[i]:=ord(s[i])-ord(0)
  else w[i]:=ord(s[i])-ord(A)+10;
  inc(ans,w[i]);
 end;
 exit(ans);
end;
begin
assign(input,kbased.in);
assign(output,kbased.out);
reset(input);
rewrite(output);
 readln(t);
 for i:=1 to t do begin
  readln(k);
  readln(s);
  fillchar(w,sizeof(w),0);
  a:=f(s);
  if a mod (k-1)=0 then writeln(yes)
  else writeln(no);
 end;
 close(input);
 close(output);
end.

2.C and.pas/c/cpp

暴力出奇迹:

20%N<=1000

另外20%:只有01

不解释O(n^2)

非暴力出满分:

【样例分析】

And去运算:0 and 0=0  0 and 1=0  1 and 0=0  1 and 1=1

 

1与第2

1与第3

2与第3

举例:5 and 23

1 and 2

1 and 1

2 and 1

        00101

and  10111

         00101

        01

and  10

        01

and  01

        10

and  01

 

     00

     01

     00

          5

另外几个数字!最大数为1 and 1=1

举例:4个数11 6 10 8

 1011

 0110

 1010

 1000

看出来了吧?

1 2 4得出的数最大!

所以,可以用贪心来解决:为使两数的and最大,故从高位开始(从左向右a[]<=109:31位到0位)枚举,看第1列的1个数有否大于等于2个;若找到,则将其它第1列为0的设为不可用(vis[MAX_N])。继续找后面位也同样处理。

取第i位是否为1a[j]>>i mod 2=1。同理第i位是否为1: a[j]>>i mod 2=0;

答案为ans:=ans+(1<<i);

var n,i,j,ans,cnt:longint;
    a:array[1..100000]of longint;
    u:array[1..100000]of boolean;
begin
assign(input,and.in);
assign(output,and.out);
reset(input);
rewrite(output);
 readln(n);
 fillchar(u,sizeof(u),true);
 for i:=1 to n do read(a[i]);
 for i:=31 downto 0 do begin
  cnt:=0;
  for j:=1 to n do begin
  if (a[j]>>i mod 2=1)and(u[j]) then inc(cnt);
  end;
  if cnt>=2 then begin
    ans:=ans+(1<<i);
    for j:=1 to n do
     if a[j]>>i mod 2=0 then u[j]:=false;
  end;
 end;
 writeln(ans);
 close(input);
 close(output);
end.

 

【数论Day3】进制问题 题解