BSGS (줄다리기 알고리즘), 북상 광 심 알고리즘

1. 도입
BSGS 알고리즘 은 줄다리기 알고리즘 이 라 고도 부 르 는데 북상 광 심 알고리즘 이 라 고도 부 르 고 큰 걸음 의 작은 걸음 알고리즘 이 라 고도 부 릅 니 다. 한 마디 로 하면 이름 이 많 지만 실제 적 으로 그 는 동 여 방정식 을 해결 하여 a, b, p 를 정 하고 가장 작은 비 마이너스 정수 x 를 구하 여 만족 시 킵 니 다. ax ≡ b(mod p)。
2. 과정
실링 x = i * m - j, 그 중 m = ceil (sqrt (p), ceil 은 위로 조정 합 니 다.
이렇게 ai*m-j = b (mod p)，
항목 이 바 뀌 었 다. ai*m = b*aj (mod p)
매 거 j (범위 0 - m), b * aj hash 표 에 저장 합 니 다.
매 거 i (범위 1 - m), hash 표 에서 첫 번 째 만족 ai * m 찾기 = b*aj (mod p)。
이때 x = i*m-j 원 하 는 거 야.
3. 이유:
실링 x = i * m - j, 그 중 m = ceil (sqrt (p), ceil 은 위로 조정 합 니 다.
이렇게 ai*m-j = b (mod p)，
항목 이 바 뀌 었 다. ai*m = b*aj (mod p)
매 거 j (범위 0 - m), b * aj hash 표 에 저장 합 니 다.
매 거 i (범위 1 - m), hash 표 에서 첫 번 째 만족 ai * m 찾기 = b*aj (mod p)。
이때 x = i*m-j 원 하 는 거 야.
템 플 릿


#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;

map mp;
ll pow(ll a,ll b,ll mod)
{
    ll ans=1;
    for(;b>0;b/=2)
    {
        if(b%2==1)
        ans=(ans*a)%mod;
         a=a*a%mod;
    }

    return ans;
}

int main()
{
    ll a,b,c;
    mp.clear();
    while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF)
    {
       if(a%c==0)
       {
           printf("No solution
");
           continue;
       }
       int flag=0;
       ll m=ceil(sqrt(c));
       ll ans;
       for(int i=0;i<=m;i++)
       {
           if(i==0)
           {
               ans=b%c;
               mp[ans]=i;
               continue;
           }
           ans=(ans*a)%c;
           mp[ans]=i;
       }
       ll cur=pow(a,m,c);
       ans=1;
       for(int i=0;i<=m;i++)
       {
           ans=(ans*cur)%c;
           if(mp[ans])
           {
                int t=i*m-mp[ans];
                printf("%d
",(t%c+c)%c);
                flag=1;
                break;
           }
       }
       if (!flag)
      printf("no solution
");

    }



    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

한 마디 로 하면 이름 이 많 지만 실제 적 으로 그 는 동 여 방정식 을 해결 하여 a, b, p 를 정 하고 가장 작은 비 마이너스 정수 x 를 구하 여 만족 시 킵 니 다. ax ≡ b(mod p)。 실링 x ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

BSGS (줄다리기 알고리즘), 북상 광 심 알고리즘

좋은 웹페이지 즐겨찾기