Gym - 101086L Chance 解答

浅浅的花香味﹌ 2022-06-10 11:18 85阅读 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