首页 > 代码库 > 【数论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*k,kn 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*k,kn 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%:只有0和1
不解释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位是否为1:a[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】进制问题 题解