问题 I: 【哈希和哈希表】门票

问题 I: 【哈希和哈希表】门票

时间限制: 1 Sec  内存限制: 128 MB
提交: 43  解决: 6
[提交] [状态] [讨论版] [命题人:admin]

题目描述

RPK要带MSH去一个更加神秘的地方！
RPK带着MSH穿过广场，在第1618块砖上按下了一个按钮，在一面墙上随即出现了一个把手。RPK握住把手，打开了一扇石质大门。他们穿过悠长而芬芳的小道，走到了一扇象征时间的大门――“the gate of time”。
门上写着一个关于时间的谜题“承诺：____年”，RPK思考了一会，从容地用手指写下1万，这时，门开始发出闪光，MSH感觉到自己的心跳都快停止了。
门开了，眼前是一座美丽的神秘花园！
正当RPK和MSH准备进入的时候，突然出现了一个看门的老大爷QL。
QL：“你们干什么你们，还没买票呢！”
RPK突然想起来现金全拿去买蛋糕了，RPK很绅士的问：“能刷卡么？我身上没现金。”
QL：“没钱？那你们不能进去！”
RPK（汗）：“……”
QL：“等等，我这有道不会的数学题，你解了我就让你们进去。”
（众人：“……”）
有一个数列{an}，a0=1，ai+1=（A*ai+ai mod B）mod C，要求这个数列第一次出现重复的项的标号。
这点小问题当然难不倒数学bug男RPK了，仅凭心算他就得到了结果。

输入

一行3个数，分别表示A B C

输出

输出第一次出现重复项的位置，如果答案超过2000000 输出-1

样例输入

2 2 9

样例输出

4

提示

30%的数据A B C≤105
100%的数据 A B C≤109

map超时了，搜了下题解学习了下hash表，怎么说呢，和链式前向星有点像，或者说邻接表，

就是将每一项的值%一个数，获得一个值作为一个数组的下标，如果这个出现过，用链式前向星或者说邻接表

的想法去存一下，这样找的时候相当于遍历一个节点的邻接表，嗯，就是这样

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2200000,Mod = 2181271;

int Hash[maxn];

struct Point{

ll val;

int next;

}p[maxn];

bool Count(int pos,ll x){

for(int i=Hash[pos]; i ;i = p[i].next)

if(p[i].val == x)

return 1;

return 0;

}

int A,B,C;

int main(){

ll a = 1;

Hash[1] = p[1].val = 1;

scanf("%d%d%d",&A,&B,&C);

for(int i=1;i<=2000000;i++){

a = (a*A + a%B )%C;

int pos = a%Mod;

if(Count(pos,a)){

printf("%d\n",i);

return 0;

}

p[i+1] = {a,Hash[pos]};

Hash[pos] = i+1;

}

printf("-1\n");

return 0;

}

网址：问题 I: 【哈希和哈希表】门票 https://www.yuejiaxmz.com/news/view/46087

相关内容

如何应对三个月哈士奇拉稀问题（宠物养护的小常识——解决哈士奇拉稀问题）
《生活中的金融学：哈佛金融通识课》[美]米希尔·A. 德赛【文字版
行前必读，超详细的哈尔滨旅游攻略，雪乡注意事项，哈尔滨雪乡5日游
纽约旅游指南【2024】曼哈顿游玩全攻略
【哈弗H6 】 2013款哈弗H6运动版报价
2024哈尔滨最全旅游攻略(最佳时间+必去景点+美食推荐)
导筒现场 · 哈尔滨 / 温州｜闫啸林《菠萝凤梨》
初出茅庐的哈士奇——宠物爱好者不可错过的小幸福（教你如何照顾刚出窝的哈士奇宝宝）
哈啰出行下载
哈尔滨旅游攻略

随便看看