手計算は雰囲気でやっていたので、プログラムに表すのに苦労した
何か変な場所が勝手に大きくなって強調されて双子調になってる 厳しい
一次不定方程式ax+by=cの解を求める
与式はax≡c(mod b)と同じ
bx≡0(mod b)と上の二つをもとにしてxの係数を減らしていき、x=1を求める
--以上と以下で変数は別物--
c%gcd>0なら解なしなので-1を返す
a,b,cをgcdで割り、aとbは互いに素となる
フェルマーとか中国幼女とかの定理から式二つで十分であることがわかる
「ax≡c&&bx≡d (mod m)なる0以上の最小のxを求める」という問題を、
同じ形のaやbが減った問題に変形していく
具体的には、(a%b)≡c-a/b*d が導かれる
a>bならaが減少するので、そうなるようにswapする
ll rem(ll x,ll mod){x%=mod;
if
(x<0)x+=mod;
return
x;}
ll gcd(ll a,ll b){
if
(a<b)swap(a,b);
return
(b?gcd(a%b,b):a);}
ll lcm(ll a,ll b){
return
a*b/gcd(a,b);}
ll euclid(ll a,ll b,ll c){
ll g=gcd(a,b);
if
(c%g>0)
return
-1;
a/=g,b/=g,c/=g;
ll q1=a,q2=b,r1=c%b,r2=0;
while
(1){
if
(q1<q2){swap(q1,q2); swap(r1,r2);}
if
(q2==1)
return
rem(r2,b);
r1=rem(r1-q1/q2*r2,b);
q1%=q2;
}
}
aやbの減少は乗算に従うので、対数時間で求まる
オーダーはlog(黄金比,a)くらいになるらしい