판자: 중국 잉여 정리 (CRT) 및 중국 잉여 정리 확장
약술 하 다
주로 많은 알고리즘 의 확장 에 사용 되 는데 만약 에 모 수가 소수 가 아니라면 많은 알고리즘 이 효력 을 잃 기 때문에 이 를 질 인 수 를 분해 한 다음 에 중국의 잉여 정리 에 따라 합병 하면 된다.
본인 은 지금 증명 에 관여 하지 않 고 결론 만 내 려 야 합 니 다.
알고리즘 프로 세 스
나머지 는 c [i] 이 고 모드 는 m [i] 이 며 M 을 m [i] 의 합 으로 한다 면 최종 답 은 c [i] (M / m [i]) inv ((M / m [i), m [i]) 와 modM 해 는 유일한 것 이 고 모든 mod 가 m 개의 다른 상황 이기 때문에 모든 상황 을 포함 할 수 있 습 니 다.
코드
LL c[maxn],m[maxn],M;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
LL getInv(LL a,LL mod)
{
LL x,y,d;
d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
}
LL CRT(int n)
{
M=1;
for(int i=1;i<=n;i++)M*=m[i];
LL ret=0;
for(int i=1;i<=n;i++)
ret=(ret+c[i] * (M/m[i]) %M * getInv(M/m[i],m[i]) )%M;
return ret;
}중국의 잉여 정 리 를 확장 하 다.
약술 하 다
모 가 서로 채식 을 하지 않 을 때 는 이 걸 써 야 한다.이것 도 서로 채식 할 때의 문 제 를 해결 할 수 있 는데, 사상 은 방정식 을 두 개 로 합 치 는 것 이다.
코드
LL gcd(LL a,LL b)
{
return !b?a:gcd(b,a%b);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
LL getInv(LL a,LL mod)
{
LL x,y;
LL d=exgcd(a,mod,x,y);
return d==1?(x+mod)%mod:-1;
}
LL exCRT(int n)
{
LL m1,m2,c1,c2,d;
for(int i=2;i<=n;i++)
{
m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i];
d=gcd(m1,m2);
if((c2-c1)%d)return -1;//
m[i] = m[i-1] * m[i] / d;
c[i] = (c2-c1)/d * getInv(m1/d,m2/d) % ( m2 / d ) * m1 + c1;
c[i] = ( c[i] % m[i] + m[i] ) % m[i];
}
return c[n];
}최종 답 은 마지막 방정식 의 c 와 m 이다.
그러나 어쨌든 모 수의 곱 은 너무 크 면 안 되 고 저장 할 수 있어 야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STL 학습노트(6) 함수 객체모방 함수는 모두pass-by-value이다 함수 대상은 값에 따라 전달되고 값에 따라 되돌아오기 때문에 함수 대상은 가능한 한 작아야 한다(대상 복사 비용이 크다) 함수 f와 대상 x, x 대상에서 f를 호출하면:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
