poj 2939 Flavius Josephus Reloaded (hash)
1180 단어 hash
http://poj.org/problem?id=2939
: , , , ;
#include<stdio.h>
#define inf 1000009
struct node
{
__int64 q;
int num;
int next;
}p[inf];
int link[inf],m;
void init()
{
for(int i=0;i<=inf;i++)
{
link[i]=0;
}
m=1;
}
int find(__int64 q,int x)
{
int i;
for(i=link[x];i>0;i=p[i].next)
{
if(q==p[i].q)
{
p[i].num++;
return p[i].num;
}
}
return 0;
}
void add(__int64 q,int x)
{
p[m].q=q;
p[m].num=1;
p[m].next=link[x];
link[x]=m++;
}
int main()
{
int n,a,b;
while(scanf("%d",&n),n)
{
scanf("%d%d",&a,&b);
init();
__int64 x=b%n;
int ans = 0;
while(1)
{
int temp=find(x,x%inf);
if(temp==0)
add(x,x%inf);
else
if(temp==2)ans++;
else if(temp==3)break;
x=(((a*x)%n*x)%n+b)%n;
}
printf("%d
",n-ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
해시란 무엇입니까?해시 함수는 단순히 임의 길이의 입력 X를 고정 길이 n의 출력 h(x)에 매핑하는 함수입니다. ” The input to a hash function is called a pre-image, the message,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.