首页 > 代码库 > 【数论Day4】 数学 题解

【数论Day4】 数学 题解

题目:http://www.cnblogs.com/ljc20020730/p/7041033.html

1.离散函数(function.pas/c/cpp)

观察右图,图像必须符合任意两点都在直线的下方。故三条直线中只有相邻两顶点之间的连线的斜率最大。故得出一个规律:最大斜率的直线一定由x坐标相邻的两点确定,即Xi-Xi-1最大的点对。

O(n)枚举,通过本题。

技术分享

var n,i,ans1,ans2,maxk:longint;
    a:array[1..200000]of longint;
begin
 assign(input,function.in);
 assign(output,function.out);
 reset(input);
 rewrite(output);
 readln(n);
 for i:=1 to n do readln(a[i]);
 ans1:=0;
 ans2:=0;
 maxk:=-maxlongint;
 for i:=2 to n do
  if a[i]-a[i-1]>maxk then begin
   maxk:=a[i]-a[i-1];
   ans1:=i-1;
   ans2:=i;
  end;
 writeln(ans1, ,ans2);
 close(input);
 close(output);
end.

2.能量采集(energy)

由于n和m都不超过1000,考虑O(n2)枚举每个植物。

通过观察,对于植物(a,b),它与(0,0)连线上植物的被挡住的数量,三条虚线处:

 (2,3)  有1个

 (4,4)  有3个

 (4,2)  有1个

  好似与a,b数值的最大公约数数有关。

则每一个坐标点被挡住的个数等于gcd(a,b)-1。

技术分享

var n,m,i,j,sum,k:longint;
function gcd(a,b:longint):longint;
begin
 if a mod b=0 then gcd:=b
 else exit(gcd(b,a mod b));
end;
begin
assign(input,energy.in);
assign(output,energy.out);
reset(input);
rewrite(output);
 readln(n,m);
 for i:=1 to n do
  for j:=1 to m do begin
   k:=gcd(i,j)-1;
   inc(sum,2*k+1);
  end;
  writeln(sum);
close(input);
close(output);
end.

 

3.大逃亡(escape.c/cpp/pas)

技术分享

注意:由于数据范围很大存实型和整型时要注意用int64和extended.

 

var v2,d2,v1,d1:int64;
    t:extended;
function f1(t:extended):extended;
begin
 exit((d1+v1*t)*(d1+v1*t)+(d2-v2*t)*(d2-v2*t));
end;
function f2:double;
begin
 exit(-(v1*d1-v2*d2)/(v1*v1+v2*v2));
end;
begin
 assign(input,escape.in);
 assign(output,escape.out);
 reset(input);
 rewrite(output);
 readln(v2,d2,v1,d1);
 if f2<=0 then t:=0
 else t:=f2;
 writeln(sqrt(f1(t)):0:6);
 close(input);
 close(output);
end.

【数论Day4】 数学 题解