Gym - 101086L Chance 解答

浅浅的花香味﹌ 2022-06-10 11:18 107阅读 0赞

## Input ##

The first line of input contains an integer *T* (1 ≤ *T* ≤ 105), the number of test cases.

Each test case will consist of two space - separated integers: *L* and *R* (0 ≤ *L* ≤ *R* ≤ 105).

## Output ##

For each test case, print the number of integers between *L* and *R* that have a prime number of ones in their binary representation.

## Example Input ##

3
    2 10
    1 19
    3 101

## Output ##

6
    13
    65

##     ##

## 题意： ##

把一个区间【L,R】中，所有正数都用其二进制表示出来，若 这些整数的 二进制表示中 1 的个数 为质数，则计数。求区间【L,R】中，求符合规则的整数 个数。

## AC代码：    ##

#include<cstring>   //AC
    #include<cmath>
    #include<cstdio>
    
    int value[100000+10];   //value[i] 是 记录从 0 到 i 中，二进制表示中，含有质数个 1 的整数的数目
    int prim[20];
    
    int main()
    {
        memset(value,0,sizeof(value));
    	value[1]=0;value[0]=0;
    
        memset(prim,0,sizeof(prim));
    	prim[2] = prim[3] = prim[5] = prim[7] = 1;
    	prim[11]= prim[13] =prim[17]=1;    //因为 2^17 = 13172 > 1e5,所以到17就好
    
    	for(int i=2;i<=100005;i++)  //打表
    	{
    		int temp = i;
    		int sum = 0;
    		while(temp)
    		{
    		    if(temp%2==1)
                            ++sum;
    		    temp/=2;
    		}
    		if(prim[sum] == 1) //这样做，挺好，比利用for循环或者 set 去找方便 （学习的地方）
                        value[i]=value[i-1]+1;
    		else
                        value[i]=value[i-1];
    	}
    	int T,L,R;
    	scanf("%d",&T);
    	while(T--) {
    		scanf("%d%d",&L,&R);
            printf("%d\n",value[R]-value[L-1]);
    	}
    	return 0;
    }

学习代码： http://www.7zhang.com/index/cms/read/id/445544.html

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关 gym224647B

gym224647B 题意： > 在二维平面中·选出一个面积最小的三角形，输出这个三角形面积的两倍。解法： > 首先，最优解一定在相邻最近的三个点...

青旅半醒/ 2024年04月20日 10:31/ 0 赞/ 88 阅读

相关 Gym - 100199C

Gym - 100199C 题意： > 其实这么长的英文题面就是想告诉我们这个题是丢手绢。解法： > 找到与 $ N $ 互质的最大整数 $ K ...

╰+哭是因爲堅強的太久メ/ 2024年04月20日 10:29/ 0 赞/ 87 阅读

相关 gym第一个程序

gym安装完成之后，在pycharm中尝试运行以下代码 import gym import time env = gym.make('CartPole

电玩女神/ 2023年01月11日 09:07/ 0 赞/ 106 阅读

相关 GYM 100685 K

乱搞题统计每一个不是magic word的单词，然后每个make\_pair 然后按照公式计算答案。因为这里是乱序的统计make\_pair的情况，所以如果相邻

比眉伴天荒/ 2022年08月04日 14:41/ 0 赞/ 137 阅读

相关 HMC5883L常见问题解答

HMC5883L常见问题解答：本文来源于百度文库： [http://wenku.baidu.com/link?url=eDNpt5pwY5nzmez2HfAgFNg7il

╰+哭是因爲堅強的太久メ/ 2022年08月01日 15:46/ 0 赞/ 243 阅读

相关 L - 01 Gym - 101078L——数学+double精度

Think: 1知识点：数学+double精度 2题意：给定1个长度不超过4000的01字符串，通过交换两个字符的位置，使得最终状态第一部分全部为0第二部分全部为1，每

超、凢脫俗/ 2022年06月10日 20:10/ 0 赞/ 126 阅读

相关 Gym - 101086A （待续）

我的AC代码：G++ 405ms include<algorithm> //AC include<cstdio> usin

桃扇骨/ 2022年06月10日 11:37/ 0 赞/ 192 阅读

相关 Gym - 101086L Chance 解答

Input The first line of input contains an integer T (1 ≤ T ≤ 105), the numb

浅浅的花香味﹌/ 2022年06月10日 11:18/ 0 赞/ 108 阅读

相关 Gym - 101201H

![70][] 题意：有k个区间，用他们填满1~n，不允许重叠，问留下的空隙最少是多少思路：可以从两方面考虑，第一个是正面考虑，转移方程dp\[i\]=min(dp\[j

野性酷女/ 2022年05月14日 12:51/ 0 赞/ 120 阅读

相关 gym101915e

include <bits/stdc++.h> define N 10 using namespace std; int a

快来打我*/ 2022年04月24日 11:16/ 0 赞/ 128 阅读