手計算は雰囲気でやっていたので、プログラムに表すのに苦労した
何か変な場所が勝手に大きくなって強調されて双子調になってる 厳しい
一次不定方程式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)くらいになるらしい
