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

【数论Day4】 数学 题解

2024-10-07 19:06:39   217人阅读

题目：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】 数学 题解


联系
我们