PAT A1078

以你之姓@ 2022-03-07 00:20 156阅读 0赞

![clipboard.png][]  
这道题牵扯到了hash散列中的集中查询方式，随后做一个总结，对于素数方面，没有神马难度；

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<vector>
    #include<math.h>
    using namespace std;
    using std::vector;
    const int maxn=10010;
    bool vis[maxn]={false};
    
    bool isPrime(int x){
        if(x<=1)
            return false;
        int sqr=sqrt(x*1.0);
        for(int i=2;i<=sqr;i++){
            if(x%i==0)
                return false;
        }
        return true;
    }
    
    int main(){
        vector<char> v;
        int m,n;
        int num;
        scanf("%d%d",&m,&n);
        while(!isPrime(m)){
            m++;
        }
        for(int i=0;i<n;i++){
            scanf("%d",&num);
            int M=num%m;
            if(!vis[M]){
                vis[M]=true;
                if(i==0)
                    printf("%d",M);
                else
                    printf(" %d",M);
            }else{
                int step;
                for(step=1;step<m;step++){
                    M=(num+step*step)%m;
                    if(!vis[M]){
                        vis[M]=true;
                        if(i==0)
                            printf("%d",M);
                        else
                            printf(" %d",M);
                        break;
                    }
                }
                if(step>=m){
                    if(i>0)
                        printf(" ");
                    printf("-");
                }
            }
        }
        for(int i=0;i<v.size();i++){
            if(i==0)
                printf("%c",v[i]);
            else
                printf(" %c",v[i]);
        }
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20220307/19941d27a5924e98abd102ada63cdec0.png

发表评论取消回复

表情：

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

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

相关阅读

相关 PAT（甲级）1078 Hashing (25point(s))

题目题目链接思路先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；代码#include <iostream>#include <str...

阳光穿透心脏的1/2处/ 2024年05月08日 05:59/ 0 赞/ 85 阅读

相关 PAT~乙级~1078 字符串压缩与解压 ~python

目描述：文本压缩有很多种方法，这里我们只考虑最简单的一种：把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 `ccccc` 就用 `5...

骑猪看日落/ 2024年04月19日 14:57/ 0 赞/ 56 阅读

相关 PAT甲级1078 hashing

题目大意：利用除留余数法建hashtable，然后利用平方探查法缓解hash值冲突问题，然后要你输出每个输入的值在hashtable中的下标位置，如果不存在的话输出 -

深碍√TFBOYSˉ_/ 2023年07月24日 13:13/ 0 赞/ 20 阅读

相关 Python实现Pat 1078. Hashing (25)

Pat 1078. Hashing (25) The task of this problem is simple: insert a sequence of disti

男娘i/ 2022年06月05日 06:56/ 0 赞/ 201 阅读

相关 (PAT 1078) Hashing (哈希表冲突处理)

The task of this problem is simple: insert a sequence of distinct positive integers into

柔光的暖阳◎/ 2022年03月18日 02:22/ 0 赞/ 209 阅读

相关 PAT A1121

![clipboard.png][] 水题，但是通过这一题需要改进一点；对于hash赋初值的时候一定要谨慎一点，不要随便赋值0，视输入的数据而定； inclu

今天药忘吃喽~/ 2022年03月07日 10:44/ 0 赞/ 189 阅读

相关 PAT A1029

![clipboard.png][] 起先自己想尝试性的直接排序找中位数，内存直接超限；其实这道题可以采用归并排序的思路来做：但是示例依旧白给。。。不过还是展现了

﹏ヽ暗。殇╰゛Y/ 2022年03月07日 10:24/ 0 赞/ 218 阅读

相关 PAT A1043

![clipboard.png][] 简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。 include<iostream> include

迷南。/ 2022年03月07日 03:46/ 0 赞/ 198 阅读

相关 PAT A1078

![clipboard.png][] 这道题牵扯到了hash散列中的集中查询方式，随后做一个总结，对于素数方面，没有神马难度； include<iostream>

以你之姓@/ 2022年03月07日 00:20/ 0 赞/ 157 阅读

相关 PAT A 1025 PAT Ranking

1025 PAT Ranking (25 分) Programming Ability Test (PAT) is

怼烎@/ 2022年02月01日 10:53/ 0 赞/ 200 阅读