Prime K tuple 문제 좀 풀어주세요ㅜ- ㅠ

  • zelos89
    zelos89

    베트남 리저널 2007년 C번 좀 도와주세요,ㅎ
    C만 푼팀도 있는데 도저히 모르겠네요ㅜ
    입력으로 자연수 a, b, k, s가 주어지는데
    [a, b]에서 연속된 k개의 소수에서 처음과 끝의 차이가 s인 튜플의 개수를 출력하는 문제에요.
    원문 :
    C. Prime k-tuple

    {p1,..., pk : p1 < p2 <...< pk} is called a prime k -tuple of distance s if p1, p2,..., pk are consecutive prime numbers and pk - p1 = s . For example, with k = 4 , s = 8 , {11, 13, 17, 19} is a prime 4-tuple of distance 8.
    Given an interval [a, b] , k , and s , your task is to write a program to find the number of prime k -tuples of distance s in the interval [a, b] .

    Input
    The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
    For each data set, there is only one line containing 4 numbers, a , b , k and s (a, b < 2 * 109, k < 10, s < 40) .

    Output
    For each test case, write in one line the numbers of prime k -tuples of distance s .

    Sample Input

    1
    100 200 4 8

    Sample Output

    2

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    저라면 a 와 b 를 1천만 정도 단위로 잘라서 precalc 해두겠는..데 ^^; 잘은 모르겠네요.작년에 베트남간 빙님이 대답해주실듯?


    13년 전 link
  • josh
    josh

    a, b < 2*10^9 는 블러프였는지 그냥 일반적인 해를 제출했더니 됐다고 하네요...


    13년 전 link
  • JongMan
    JongMan

    아 실로 막나가는 베트남이로군요....;;


    13년 전 link
  • hyunhwan
    hyunhwan

    서버상에서의 Time Limit을 체크해봤는데 180초네요 =_=);;
    그리고 다음과 같은 코드를 통해 테스트를 해봤는데 Runtime Error라는 결과가 나오는것 보니 딱히 입력에 대해 블러핑을 한거 같지는 않습니다.

    #include <stdio.h>
    #include <assert.h>
    typedef long long ll;
    int main() {
        int tn;
        ll a, b, c, d;
        scanf("%d",&tn);
        while(tn--) {
            scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
            if(a >= 1e9 || b >= 1e9 ) assert(false);
        }
    }
    

    13년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.