AtCoder Beginner Contest 084 D-2017-like Number(区間問題a[r]-a[l-1])

2379 ワード

Problem Statement
We say that a odd number N is similar to 2017 when both N and (N+1)⁄2 are prime.
You are given Q queries.
In the i-th query, given two odd numbers li and ri, find the number of odd numbers x similar to 2017 such that li≤x≤ri.
Constraints
1≤Q≤105
1≤li≤ri≤105
li and ri are odd.
All input values are integers.
Input
Input is given from Standard Input in the following format:
Q
l1 r1
:
lQ rQ
Output
Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.
Sample Input 1
1
3 7
Sample Output 1
2
3 is similar to 2017, since both 3 and (3+1)⁄2=2 are prime.
5 is similar to 2017, since both 5 and (5+1)⁄2=3 are prime.
7 is not similar to 2017, since (7+1)⁄2=4 is not prime, although 7 is prime.
Thus, the response to the first query should be 2.
Sample Input 2
4
13 13
7 11
7 11
2017 2017
Sample Output 2
1
0
0
1
Note that 2017 is also similar to 2017.
Sample Input 3
6
1 53
13 91
37 55
19 51
73 91
13 49
Sample Output 3
4
4
1
1
1
2
題意:[l,r]内の2017と類似する数字を判断し、2017の性質:2017は素数、(2017+1)/2は素数である.
構想:表を打って1-10^5内のそれぞれの数字を計算して、それから結果はa[r]-a[l-1].(区間問題はずっと私の1つの弱点で、[l,r]が3と7の倍数が何個の問題を探すのに似ていて、私はHNUSTの上でWAで20発!!)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 100005
using namespace std;
typedef long long ll;
int vis[N],a[N];
void creat()
{
    for(int i=2; i<=400; i++)
    {
        if(!vis[i])
        {
            for(int j=i*2; j<=N; j+=i)
                vis[j]=1;
        }
    }
}
int main()
{

    memset(vis,0,sizeof(vis));
    creat();
    vis[1]=1;
    int sum=0,n;
    for(int i=1; i<=N; i++)
    {
        if(i%2==1)
        {
            if(vis[i]==0&&vis[(i+1)/2]==0)
                sum++;
        }

        a[i]=sum;
    }
    while(scanf("%d",&n)==1)
    {
        while(n--)
        {
            int c,b;
            scanf("%d%d",&c,&b);

            printf("%d
",a[b]-a[c-1]);
        }
    }
}

[規格10999]カウントソート(正解率23%)

[BMI計算機3]Series&Navigation