Contest2257 - 抗击疫情，从我做起--大中小学生联合训练赛第五十二场

Contest2257 - 抗击疫情，从我做起--大中小学生联合训练赛第五十二场

题目

​​问题 E: 喜爱​​​​问题 I: Mysterious Light​​

问题 E: 喜爱

题目描述小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。 现在，小s想知道，对于一个区间[L,R]，有多少数是他所喜爱的。输入输入包含多组数据。 输入第一行T，表示数据组数。 每组数组仅有一行，包含两个正整数[L,R]。输出对于每组数据输出一行，表示答案。样例输入 Copy2 5 10 2015 2015样例输出 Copy2 1提示对于30%的数据:L,R≤106，T≤10 对于60%的数据:L,R≤1010，T≤100 对于100%的数据:L,R≤1018，T≤10000

题意分析 就是要求出一个区间内二进制表示情况下只含一个0的个数；思路分析 ：先说明一个最最最重要的: 左移右移无法让数字达到1e10以上就这个地方凉凉了好久；就下来是我的思路：1 ：首先打表是必不可少的，要不你每次都要运行肯定不行；我是按2进制位数打的表这样我感觉简单点，（简单就是一下 怎么打的表：如果2进制有x位 会有x-1个可行的值，所以就可以了）；2 :因为由于左右两个界限你可以先从右界限开始看：找到他二进制位数的下一位，（这样才会比这个数值大），用快速幂表示出来（我一开始用的左移，不行）；然后让这个数-1，（目的是让其二进制位全部为1）这样只要分别减去2i判断与右端点的大小既可以了判断这个是否符合题意了；3：与2一样判断左界限，不过这时是大于等于左界限符合条件4：因为两端的已经求出来了，直接用我们打好的表来表示中间的那部分，即a[右端点二进制位]-a[左端点二进制位+1]；这样就是所求，别忘了每次初始化呦。

里面的注释代表我修改过的痕迹，呜呜呜~~~~

#include

问题 I: Mysterious Light

Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of Mysterious Light.

Three mirrors of length N are set so that they form an equilateral triangle. Let the vertices of the triangle be a,b and c.

Inside the triangle, the rifle is placed at the point p on segment ab such that ap=X. (The size of the rifle is negligible.) Now, the rifle is about to fire a ray of Mysterious Light in the direction of bc.

The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as “ordinary” light. There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror! When the ray comes back to the rifle, the ray will be absorbed.

The following image shows the ray’s trajectory where N=5 and X=2.

It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of N and X. Find the total length of the ray’s trajectory.

Constraints 2≦N≦1012 1≦X≦N−1 N and X are integers. Partial Points 300 points will be awarded for passing the test set satisfying N≦1000. Another 200 points will be awarded for passing the test set without additional constraints.

输入

The input is given from Standard Input in the following format:N X

输出

Print the total length of the ray’s trajectory.

样例输入 Copy

5 2

样例输出 Copy

12

提示

Refer to the image in the Problem Statement section. The total length of the trajectory is 2+3+2+2+1+1+1=12. 思路：就是列出来一部分 找出规律。 代码：

#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。