day 10 - 데이터 구조 실험 찾기 5: 제곱 의 해시 표

데이터 구조 실험의 찾기 5: 제곱 의 해시 표
Time Limit: 400 ms Memory Limit: 65536 KiB
Problem Description
주어진 중복 데이터 가 없 는 정수 입 니 다. 주어진 해시 함수 에 따라 대응 하 는 hash 표를 만 듭 니 다. 해시 함 수 는 H (Key) = Key% P 이 고 P 는 해시 표 길이 이 며 P 는 소수 입 니 다. 충돌 을 처리 하 는 방법 은 제곱 탐측 방법 으로 증분 di = ± i ^ 2, i = 1, 2, 3,..., m - 1 을 사용 합 니 다.
Input
EOF 가 끝 날 때 까지 여러 그룹의 테스트 데 이 터 를 입력 하 십시오.
각 그룹의 데이터 의 첫 번 째 줄 은 두 개의 정수 N (N < = 500) 과 P (P > = 2N 의 최소 소수) 를 보 여 줍 니 다. N 은 해시 표 에 삽입 할 요소 의 개수 이 고 P 는 해시 표 의 길이 입 니 다.두 번 째 줄 은 중복 요소 가 없 는 정수 N 개 를 보 여 주 며 데이터 간 에 빈 칸 으로 간격 을 둡 니 다.
Output
입력 데이터 의 순서에 따라 해시 표 의 저장 위치 (hash 표 아래 표 시 는 0 부터) 를 출력 하고 데이터 간 에 빈 칸 간격 으로 제곱 탐지 방법 으로 충돌 을 처리 합 니 다.
Sample Input

4 11
10 6 4 15
9 11
47 7 29 11 9 84 54 20 30

Sample Output

10 6 4 5
3 7 8 0 9 6 10 2 1

 
#include #include
int main(void) {     int n, p, x = 1, a, k, i, j;     int h[10005], t[10005];     t[0] = 0;
    for(i = 1; i < 100; i += 2)     {         t[i] = x * x;         t[i + 1] = -t[i];         x++;     }
    while(~scanf("%d %d", &n, &p))     {         int ans;         memset(h, -1, sizeof(h));
        for(i = 0; i < n; i++)         {             scanf("%d", &k);             ans = 0;             for(j = 0; j < 100; j++)             {                 a = (k % p + t[j]) % p;                 if(h[a] == -1)                 {                     h[a] = k;                     ans = a;                     break;                 }
              /*  else if(h[a] == k)                 {                     ans = k;                     break;                 }*/             }
            printf("%d", ans);             if(i < n - 1)             {                 printf(" ");             }         }
        printf("");     }
    return 0;
}