问题 E: 喜爱
-
题目描述
-
小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。
现在，小s想知道，对于一个区间[L,R]，有多少数是他所喜爱的。 -
输入
输入包含多组数据。
输入第一行T，表示数据组数。
每组数组仅有一行，包含两个正整数[L,R]。 -
输出
对于每组数据输出一行，表示答案。
-
样例输入 Copy
2
5 10
2015 2015 -
样例输出 Copy
2
1 -
提示
对于30%的数据:L,R≤106，T≤10
对于60%的数据:L,R≤1010，T≤100
对于100%的数据:L,R≤1018，T≤10000
- 题意分析 就是要求出一个区间内二进制表示情况下只含一个0的个数；
- 思路分析 ： <mark>先说明一个最最最重要的: 左移右移无法让数字达到1e10以上</mark>就这个地方<mark>凉凉</mark>了好久；
- 就下来是我的思路：
1 ： 首先打表是必不可少的，要不你每次都要运行肯定不行；我是按2进制位数打的表这样我感觉简单点，（简单就是一下 怎么打的表：如果2进制有x位 会有x-1个可行的值，所以就可以了）；
2 : 因为由于左右两个界限你可以先从右界限开始看：找到他二进制位数的下一位，（这样才会比这个数值大），用<mark>快速幂</mark>表示出来（我一开始用的左移，不行）；然后让这个数-1，（目的是让其二进制位全部为1）这样只要分别减去2i判断与右端点的大小既可以了判断这个是否符合题意了；
3： 与 2一样判断左界限，不过这时是大于等于左界限符合条件
4： 因为两端的已经求出来了，直接用我们打好的表来表示中间的那部分，即a[右端点二进制位]-a[左端点二进制位+1]；
这样就是所求，别忘了每次初始化呦。
里面的注释代表我修改过的痕迹，呜呜呜~~~~
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef unsigned long long ll;
using namespace std;
const int maxn=210;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
ll n,m,k,sum,cnt;
ll a[maxn],b[maxn],dp[maxn];
char str[maxn],s[maxn];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a);
}
a=(a*a);
b/=2;
}
return ans;
}
int main(){
ll t;
cin>>t;
a[0]=1;
for(ll i=1;i<=200;i++)
a[i]=a[i-1]+i-1;
// for(ll i=1;i<=200;i++) cout<<a[i]<<" ";
while(t--){
cin>>n>>m;
sum=0;
for(int i=0;i<=200;i++)
if(m<qpow(2,i))
{
k=i;
// cout<<i<<endl;
break;
}
ll x=qpow(2,k)-1;//quan 1
// cout<<x<<endl;
for(int i=k-2;i>=0;i--)
{
if(m>=(x-qpow(2,i)))
{
sum++;
// cout<<x-(1<<i)<<endl;
}
}
for(int i=1;i<=200;i++)
if(n<qpow(2,i))
{
cnt=i;
// cout<<i<<endl;
break;
}
ll y=qpow(2,cnt)-1;
for(int i=0;i<cnt-1;i++)
if(n<=(y-qpow(2,i))){
sum++;
}
// cout<<a[k-1]<<" "<<a[cnt]<<endl;
//cout<<sum<<endl;
sum+=a[k-1]-a[cnt];
cout<<sum<<endl;
}
return 0;
}
问题 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 <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=210;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
ll n,m,k,sum,cnt;
ll a[maxn],b[maxn],dp[maxn];
char str[maxn],s[maxn];
ll gcd(ll a,ll b){
while(b){
ll temp=a%b;
a=b;
b=temp;
}
return a;
}
int main(){
ll x;
cin>>n>>x;
cout<<(n-gcd(n,x))*3<<endl;
return 0;
}
京公网安备 11010502036488号