poj 1061 개구리 의 데이트(유클리드 확장)
사고:그들 이 t 번 뛰 어 만 났 다 고 설정 하면(x+t*m)-(y+t*n)=z*l(z 는 하나의 정수 로 그들의 거리 차 이 는 l 의 z 배 임 을 나타 낸다)변형 되 었 다.
(n-m)*t + z*l = (x-y);
n-m;b = l; c = x-y;
그러면 원 식 은 a*t+z*b=c 로 변 합 니 다.
유클리드 템 플 릿 을 확장 하고 a*x+b*y=gcd(a,b)방정식 과 같은 구 해 형 을 구 합 니 다.
LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
LL d = extend_gcd(b,a%b,x,y);
LL t = x;
x = y;
y = t-a/b*y;
return d;
}방정식 a*x+b*y=c 가 풀 리 는 전 제 는 gcd(a,b)|c 이 고 이 를 바탕 으로 방정식 은 d=gcd(a,b)의 서로 다른 풀이 가 있다.그 중에서 기초 해 x0=x'*(c/d)%b(그 중 x'는 a*x'+b*y'=gcd(a,b)의 해);xi=x0+i*(b/d)로 통칭 합 니 다.
#include
#include
#include
#include
#include 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
poj 1061 개구리 의 데이트(유클리드 확장)텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
