POJ 2417 Discrete Logging（BabyStepGiantStep）
1599 단어 logging
제목:A,B,P(P 는 소수)를 정 하고 최소 x 만족 A^x%P=B 를 구하 십시오.
사고:m=ceil(sqrt(P-1),x=k*m+t 를 설정 하면 A^x=((A^m)^k)*A^t,그래서 A^t=B*((A^-m)^k)%P.A^t 의 값 과 대응 하 는 t 를 저장 합 니 다.A^-m 의 k 제곱 을 계산 하여 찾 습 니 다.
i64 P,A,B;
i64 power(i64 a,i64 b,i64 p)
{
i64 ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
struct node
{
i64 id,k;
};
node a[N];
int cmp(node a,node b)
{
if(a.k==b.k) return a.id<b.id;
return a.k<b.k;
}
i64 find(i64 low,i64 high,i64 k)
{
i64 mid;
while(low<=high)
{
mid=(low+high)>>1;
if(a[mid].k==k) return a[mid].id;
if(a[mid].k>k) high=mid-1;
else low=mid+1;
}
return -1;
}
//A^x=B(%P)
i64 babyStepGiantStep(i64 A,i64 B,i64 P)
{
i64 m=ceil(sqrt(1.0*P-1)),e=1,c=power(power(A,P-2,P),m,P),i,k,x;
FOR0(i,m) a[i].id=i,a[i].k=e,e=e*A%P;
sort(a,a+m,cmp);
k=1;
FOR1(i,m-1)
{
if(a[i].k!=a[k-1].k) a[k++]=a[i];
}
e=B;
FOR0(i,m)
{
x=find(0,k-1,e);
if(x!=-1) return i*m+x;
e=e*c%P;
}
return -1;
}
int main()
{
Rush(P)
{
RD(A,B);
i64 ans=babyStepGiantStep(A,B,P);
if(ans<0) puts("no solution");
else PR(ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CodeSite Live Viewer를 좀 더 사용해 보았습니다.로 무려 월간 업 할 수 있는 화상 용량을 넘어 버렸다 이 기사는 마지막 부분의 연속입니다. 토호호... Checkpoint 로그로 CheckPoint를 설정할 수도 있고 Live Viewer에서도 구성 가능 Liv...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
