无穷数

时限：1s内存：32M

★问题描述:

我们生成两个无穷大的数，第一个数是把所有的自然数链接起来组成的数字；第二个数是把所有自然数的平方连接起来组成的数。对这两个数求和，如下：

 123456789101112131415161718192021...

+ 149162536496481100121144169196225...

= 272619325597593231536305887388246...

现在给你一个整数k，问和从左往右数第k位的数码是多少？

★数据输入：

输入数据有多组，每组数据输入一行，有一个数k。对于100%的数据，k<=2147483647

★结果输出:

对于每组数据，输出一个整数N，从左往右数第k位的数码。

const
   a:array[1..19,1..2] of int64=((1,3),(4,9),(10,31),(32,99),(100,316),(317,999),(1000,3162),(3163,9999),(10000,31622),(31623,99999),(100000,316227),(316228,999999),(1000000,3162277),(3162278,9999999),(10000000,31622776),(31622777,99999999),
   (100000000,316227766),(316227767,999999999),(1000000000,2147483647));
var
   k:longint;
function search_ai(k:longint):longint;
var
   i,j,d,k2,g:int64;
begin
   d:=1;i:=9;
   while (true) do
   begin
      if (k-d*i>0) then
      begin
         dec(k,d*i);
         i:=i*10;inc(d);
      end
      else break;
   end;
   k2:=i div 9+(k-1) div d;
   g:=(k-1) mod d+1;
   g:=d-g+1;
   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
{
function search_bi(k:longint):longint;
var
   i,j:int64;
   head:longint;
begin
   head:=1;j:=10; i:=1;
   while (i<=2147483647 ) do
   begin
      if ((i*i) div j>0) then
      begin
         write('(',head,',',i-1,')',',');
         head:=i; j:=j*10;
      end;
      inc(i);
   end;
end;      }


function search_bi(k:longint):longint;
var
   i:longint;
   g,k2:int64;
begin
   i:=1;
   while (k>i*(a[i,2]-a[i,1]+1)) do
   begin
      dec(k,i*(a[i,2]-a[i,1]+1));
      inc(i);
   end;

   k2:=(k-1) div i+1;
   k2:=a[i,1]-1+k2;
   k2:=k2*k2;
   g:=(k-1) mod i+1;
   g:=i-g+1;

   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
function search_fi(k:longint):longint;
var
   i:longint;
begin
   i:=search_ai(k)+search_bi(k);
   if (i<=8) then exit(0)
   else if (i>9) then exit(1)
   else exit(search_fi(k+1));

end;
begin
//   assign(output,'dabiao.out');
//   rewrite(output);

   while not eof do
   begin
      readln(k);
      writeln((search_bi(k)+search_ai(k)+search_fi(k+1)) mod 10);


   end;

//   search_bi(1);
//close(output);
end.

求一个序列的最长不下降子序列的长度，与个数（相同数列算1个）

关键是如何判重。

显然如果之前有一个尾数相同且长度相同的序列，哪么后一个包含前一个所有可能的序列相同的序列，故将前一个序列删除（重复)

Program P1952;
var
   n,i,j,ans:longint;
   a,len,f,path:array[1..5000] of longint;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   for i:=1 to n do
   begin
      len[i]:=1;
      f[i]:=1;
      path[i]:=i;
      for j:=i-1 downto 1 do
         if (a[j]>a[i]) and (len[j]+1>len[i]) then
         begin
            len[i]:=len[j]+1;
            f[i]:=f[j];
         end
         else if (a[j]>a[i]) and (len[j]+1=len[i]) then inc(f[i],f[j]);


      for j:=1 to i-1 do
         if (a[i]=a[j]) and (len[i]=len[j]) then f[j]:=0;



   end;
   j:=0;
   for i:=1 to n do if len[i]>j then j:=len[i];
   ans:=0;
   for i:=1 to n do if len[i]=j then inc(ans,f[i]);

   writeln(j,' ',ans);


end.

这题是exgcd……

我居然连wa了2天……

至少知道DIV函数的性质了   （-x) div t =-(x div t)    

                           (-x) div (-t) = (x div t)

发现自己数论蒟蒻……

Program p1061;
var
   x,y,n,m,l,t:int64;
   a,b,c,c2:int64;
function exgcd(a,b:int64):int64;
var
   x1,y1:longint;
begin
   if b=0 then
   begin
      x:=1;
      y:=0;
      exit(a);
   end;
   exgcd:=exgcd(b,a mod b);
   x1:=y;
   y1:=x-(a div b)*y;
   x:=x1;
   y:=y1;
end;
begin

   read(x,y,m,n,l);
   a:=n-m;
   c:=x-y;
   b:=l;
   c2:=exgcd(a,b);
   if (c mod c2<>0) then writeln('Impossible')
   else
   begin
      x:=x*(c div c2);
      y:=y*(c div c2);
      t:=b div c2;


      if t<0 then
         while (x<0) do
         begin

            x:=x-t*abs(x div t)-t;
         end;
      if t>0 then while (x<0) do x:=x+t*abs(x div t)+t;

      x:=x mod (b div c2);
      writeln(x);
   end;


end.

格雷码做

0要特判

答案 就是读入的两个数充格雷码转为2进制的差的绝对值的十进制

Program P1832;
Type
   arr=record
       a:array[1..500] of longint;
       len:longint;
       end;
var
   n,m,i:longint;
   a,b,c,d:arr;
   node2:array[1..1000] of arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function compare:boolean;
var
   i,j:longint;
begin
   while (a.len>1) and (a.a[a.len]=0) do dec(a.len);
   while (b.len>1) and (b.a[b.len]=0) do dec(b.len);
   if a.len<b.len then exit(true)
   else if a.len>b.len then exit(false);

   i:=a.len;
   while (i>1) and (a.a[i]=b.a[i]) do
   begin
      dec(i);
   end;
   if (a.a[i]<=b.a[i]) then exit(true) else exit(false);
end;
Procedure Subtract(a,b:arr;var c:arr);
var
   i,j:longint;
   pa:arr;
begin
   if (compare) then
   begin
      pa:=a;
      a:=b;
      b:=pa;
   end;
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
   begin
      inc(c.a[i],a.a[i]-b.a[i]);
      if c.a[i]<0 then
      begin
         inc(c.a[i],2);
         dec(c.a[i+1]);
      end;
   end;
   c.len:=a.len;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
procedure add(a,b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to max(a.len,b.len) do
   begin
      inc(c.a[i],a.a[i]+b.a[i]);
      inc(c.a[i+1],c.a[i] div 10);
      c.a[i]:=c.a[i] mod 10;
   end;
   c.len:=max(a.len,b.len)+1;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
begin
   fillchar(node2,sizeof(node2),0);
   node2[1].len:=1;
   node2[1].a[1]:=1;

   for i:=2 to 500 do
   begin
      add(node2[i-1],node2[i-1],node2[i]);
   end;

 {  assign(input,'P1832.in');
   assign(output,'P1832.out');
   reset(input);
   rewrite(output);
  }
   read(m);
   while m>0 do
   begin
      fillchar(a,sizeof(a),0);
      fillchar(b,sizeof(b),0);
      read(n);

      if n=0 then
      begin
         writeln('0');
         dec(m);
         continue;
      end;
      for i:=n downto 1 do read(a.a[i]);
      for i:=n downto 1 do read(b.a[i]);
      for i:=n-1 downto 1 do
      begin
         a.a[i]:=(a.a[i] xor a.a[i+1]);
      end;

      for i:=n-1 downto 1 do
         b.a[i]:=b.a[i] xor b.a[i+1];
      a.len:=n;
      b.len:=n;

      subtract(a,b,c);
//      for i:=n downto 1 do write(c.a[i]);
//      writeln;
      fillchar(d,sizeof(d),0);
      d.len:=1;
      for i:=n downto 1 do
         if c.a[i]>0 then add(node2[i],d,d);

      for i:=d.len downto 1 do write(d.a[i]);


      writeln;
      dec(m);
   end;
{   close(input);
   close(output);
}
end.

线性筛素数……

Program P3006;
const
   maxn=1000000;
var
   prime:array[1..maxn] of boolean;
   p:array[1..maxn] of longint;
   t:longint;
   a,d,n:longint;
Procedure primeing;
var
   i,j:longint;
begin
   fillchar(prime,sizeof(prime),false);
   t:=0;
   prime[1]:=true;
   for i:=2 to maxn do
   begin
      if not(prime[i]) then
      begin
         inc(t);
         p[t]:=i;
      end;
      for j:=1 to t do
      begin
         if p[j]*i>maxn then break;
         prime[p[j]*i]:=true;
         if i mod p[j]=0 then break;
      end;
   end;
end;
begin
   primeing;
   readln(a,d,n);
   while (a+d+n>0) do
   begin
      while (n>0) do
      begin
         if not(prime[a]) then dec(n);
         inc(a,d);
      end;
      writeln(a-d);
      readln(a,d,n);
   end;
end.

中国剩余定理

若一个数除m1余p1,除m2余p2……,除mn余pn （m1,m2……,mn互质）

则求 k1使k1=m2*……*mn的倍数且除m1余1

……

则这个数为(k1*p1+k2*p2+……kn*pn) mod (m1*m2*……*mn)

Program P1005;
var
   a,b,c,d,i,a1,a2,a3,ans:longint;
begin
   i:=1;
   a1:=28*33;
   a2:=23*33;
   a3:=23*28;
   while (a1 mod 23<>1) do inc(a1,28*33);
   while (a2 mod 28<>1) do inc(a2,23*33);
   while (a3 mod 33<>1) do inc(a3,23*28);

   while (true) do
   begin
      read(a,b,c,d);
      if (a=-1) and (b=-1) and (c=-1) and (d=-1) then break;
      ans:=(a1*a+a2*b+a3*c+21252-d) mod 21252;
      if ans=0 then ans:=21252;
      writeln('Case ',i,': the next triple peak occurs in ',ans,' days.');
      inc(i);
   end;
end.

问n=a+a+1+a+2+...+a+k 的情况总数

n=(k+1)*a+(k+1)*k/2

 =(k+1)(a+k/2)

n为整数，k+1为整数，(a+k/2)为整数，k为偶数，k+1为奇数

当n和k+1确定时，a为定值

故解为n的奇因子个数

Program P2140;
var
   i,n,ans:longint;
begin
   ans:=0;
   read(n);
   i:=1;
   while (i<=n) do
   begin
      if (n mod i=0) then inc(ans);
      inc(i,2);
   end;
   writeln(ans);
end.