POJ 2417 Discrete Logging [고 차 동 여 방정식]
http://poj.org/problem?id=2417
제목 의 대의:
정수 P, B, N 만족 공식 B ^ i = N (mod P), i 의 값 이 얼마 인지 알 고 있 습 니 다.
생각:
전형 적 인 고 차 동 여 방정식 A ^ x = B (mod C) 를 풀 고 템 플 릿 으로 직접 해결 합 니 다.입력 순서 주의: C A B
AC 코드:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL __int64
using namespace std;
const int MAXN = 65535;
struct HASH
{
int a;
int b;
int next;
}Hash[MAXN*2];
int flag[MAXN+66];
int top,idx;
void ins(int a,int b)
{
int k = b & MAXN;
if(flag[k] != idx)
{
flag[k] = idx;
Hash[k].next = -1;
Hash[k].a = a;
Hash[k].b = b;
return;
}
while(Hash[k].next != -1)
{
if(Hash[k].b == b)
return;
k = Hash[k].next;
}
Hash[k].next = ++top;
Hash[top].next = -1;
Hash[top].a = a;
Hash[top].b = b;
}
int Find(int b)
{
int k = b & MAXN;
if(flag[k] != idx)
return -1;
while(k != -1)
{
if(Hash[k].b == b)
return Hash[k].a;
k = Hash[k].next;
}
return -1;
}
int GCD(int a,int b)
{
if(b == 0)
return a;
return GCD(b,a%b);
}
int ExGCD(int a,int b,int &x,int &y)
{
int temp,ret;
if(!b)
{
x = 1;
y = 0;
return a;
}
ret = ExGCD(b,a%b,x,y);
temp = x;
x = y;
y = temp - a/b*y;
return ret;
}
int Inval(int a,int b,int n)
{
int x,y,e;
ExGCD(a,n,x,y);
e = (LL)x*b%n;
return e < 0 ? e + n : e;
}
int PowMod(LL a,int b,int c)
{
LL ret = 1%c;
a %= c;
while(b)
{
if(b&1)
ret = ret*a%c;
a = a*a%c;
b >>= 1;
}
return ret;
}
int BabyStep(int A,int B,int C)
{
top = MAXN;
++idx;
LL buf = 1%C,D = buf,K;
int d = 0,temp,i;
for(i = 0; i <= 100; buf = buf*A%C,++i)
{
if(buf == B)
return i;
}
while((temp = GCD(A,C)) != 1)
{
if(B % temp)
return -1;
++d;
C /= temp;
B /= temp;
D = D*A/temp%C;
}
int M = (int)ceil(sqrt((double)C));
for(buf = 1%C,i = 0; i <= M; buf = buf*A%C,++i)
ins(i,buf);
for(i = 0,K = PowMod((LL)A,M,C); i <= M; D = D*K%C,++i)
{
temp = Inval((int)D,B,C);
int w;
if(temp >= 0 && (w = Find(temp)) != -1)
return i * M + w + d;
}
return -1;
}
int main()
{
int A,B,C;
while(~scanf("%d%d%d",&C,&A,&B))
{
B %= C;
int temp = BabyStep(A,B,C);
if(temp < 0)
printf("no solution
");
else
printf("%d
",temp);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.