#P7006. [2017年成都七中集训]chorus

    ID: 6837 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-欧拉函数莫比乌斯函数莫比乌斯反演杜教筛整除分块线性筛记忆化搜索一维前缀和交换求和顺序

[2017年成都七中集训]chorus

题目描述

平面上以原点为圆心画有无数个半圆。第 ii 个半圆半径为 ii,在上半平面内有 ii 只小鸟,它们把半圆的弧等分成 i+1i+1 段。

原点处有一位听众。如果沿同一条从原点出发的射线有多只小鸟,只有距原点最近的一只不被遮挡。被遮挡的小鸟贡献为 00,其余小鸟贡献为 cos⁡2θ\cos^2\theta,其中 θ\theta 为该射线的倾斜角。所有半圆上的小鸟都可能遮挡后面的小鸟。

求第 LL 个至第 RR 个半圆(包含两端)上的小鸟的贡献之和。

输入格式

一行两个正整数 L,RL,R。

输出格式

输出一个实数,保留两位小数。

样例

2 3
1.50

第一个半圆上的小鸟 (0,1)(0,1) 不计分,但遮挡了第三个半圆上的 (0,3)(0,3)。第二个半圆上角度为 60∘,120∘60^\circ,120^\circ 的小鸟各贡献 14\frac14,第三个半圆上角度为 45∘,135∘45^\circ,135^\circ 的小鸟各贡献 12\frac12。

数据范围

  • 对于 30%30\% 的数据,R≤3000R\le 3000。
  • 对于另外 10%10\% 的数据,L=RL=R 且 L+1L+1 是某个质数的两倍。
  • 对于另外 10%10\% 的数据,L=RL=R 且 L+1L+1 是质数。
  • 对于另外 5%5\% 的数据,L=RL=R 且 L+1L+1 是某个质数的平方。
  • 对于另外 5%5\% 的数据,L=RL=R。
  • 对于 70%70\% 的数据,R≤106R\le 10^6。
  • 对于 85%85\% 的数据,R≤107R\le 10^7。
  • 对于所有数据,0<L≤R≤1080<L\le R\le 10^8。

提示:cos⁡2θ=(cos⁡2θ+1)/2\cos^2\theta=(\cos 2\theta+1)/2。

原 PDF 题面