類ユークリッドアルゴリズムの小結
基本定義
f(a,b,c,n)=Σni=0⌊ai+bc⌋g(a,b,c,n)=Σni=0 i⌊ai+bc⌋h(a,b,c,n)=Σni=0⌊ai+bc⌋2 m=⌊an+bc⌋
fを押す
a>=cまたはb>=cの場合、f(a,b,c,n)=(a/c)∗n∗(n+1)/2+(b/c)∗(n+1)+f(a%c,b%c,c,n)が容易に得られる.f(a,b,c,n)=Σni=0Σmj=1[(ai+b)/c>=j]という式は幾何学的に理解できる.fの式の意味は、実際には、x=0とx=nの2本の鉛直線からなる直角台形内の整点数(縦座標が0の点を含まず、オンライン上の点を含む)である.次に私たちのこの式は1本の縦線を列挙して、上の整点の個数を統計して、私たちは今1本の横線を列挙して、横線の上の整点の個数を統計して、この式です.f(a,b,c,n)=Σni=0Σm−1 j=0[(ai+ b)/c>=j+1]f(a,b,c,n)=Σni= 0Σm−1 j=0[ai>= cj+c−b]f(a,b,c,n)=Σni= 0Σm−1 j=0[ai> cj+c−b−b−1 j=0[ai> cj+c−b−b−1]f(a,b,c,n)=Σni= 0Σm−1 j=0[i>(cj+c−b−b−b−1)/aa/a(a,b(a,b,n)=0Σni= 0Σm−1 j=0Σm]f(a,b,c,n)=Σmj=0(n−(cj+c−b−1)/a)f(a,b,c,n)=nm−f(c,c−b−1,a,m−1)は再帰処理を継続する.第1および第3次元表現状態のみを見ると,(a,c)から(c,a%c)になるたびに複雑度はユークリッドアルゴリズムと一致することが分かった.
gを押す
a>=cまたはb>=cの場合、g(a,b,c,n)=(a/c)∗n∗(n+1)∗(2 n+1)/6+(b/c)∗n∗(n+1)/2+g(a%c,b%c,c,n)が得られやすい.まずまずfと同じように下取りを変えてg(a,b,c,n)=Σni=0 iΣmj=1[(ai+ b)/c>=j]g(a,b,c,n)=Σni= 0 iΣm−1 j=0[i>(cj+c−b−b−1)/a]g(a,b,c,n)=1/2∗Σm−1−1 j=0(n+1+(cj+c−b−1)/a)n−(n−(cj+c−c−b−b−b−b)−b(b−(cj+c−c−b−b−b−b−b−b)−b(c−b−b−b−b−b)−b(c−1)/a)ここで見るのは少しつらいが,fのときに転化するのは実は0次方和であり,gは1次方和であり,だからここでは求和式を使いました.g(a,b,c,n)=1/2∗Σm−1 j=0 n(n+1)−(cj+c−b−1)/a−[(cj+c−b−1)/a]2 g(a,b,c,n)=1/2∗[n(n+1)m−f(c,c−b−1,a,m−1)−h(c,c−b−b−1,a,a,m−1)−b−1,a,m−1)]が取り外されたのはgが面倒なようで、hを押す必要がある.
プッシュh
a>=cまたはb>=cの場合、hも面倒なのですが・・・三項式の二乗は、多分こんなh(a,b,c,n)=(a/c)2∗n(n+1)(2 n+1)/6+(b/c)2∗(n+1)+(a/c)∗(b/c)∗n(n+1)+h(a%c,b%c,b%c,c,c,c,c)+2∗(a%c,b%c,c,+2)+2∗g(a%c,b%c,c,+n)+2)+2∗(a%c,+2)+2(a%c,+2,+c,∗(b/c)∗f(a%c,b%c,c,n)次にaとbがcより小さい場合、考え方を変えましょう.どのようにしてn^2を手に入れますか?n 2=2∗n(n+1)2−n=2Σni=0 i−nと考えられるh(a,b,c,n)=Σni=0(2∗Σ(ai+b)/cj=1 j−(ai+b)/c)を押すと交換主体が考えられる.h(a,b,c,n)=2∗∑m−1j=0(j+1)∗∑ni=0[(ai+b)/c>=j+1]−f(a,b,c,n) h(a,b,c,n)=2∗∑m−1j=0(j+1)∗∑ni=0[i>(cj+c−b−1)/a]−f(a,b,c,n) h(a,b,c,n)=2∗∑m−1j=0(j+1)∗(n−(cj+c−b−1)/a)−f(a,b,c,n) h(a,b,c,n)=nm(m+1)−2g(c,c−b−1,a,m−1)−2f(c,c−b−1,a,m−1)−f(a,b,c,n)
インプリメンテーション
私の実装はf,g,hのそれぞれの値を直接返すのが簡単です.境界はaが0で、3つの0を返します.upd:境界を書き間違えたようですから、みんなで押してください.ブスだし、強制変換しても無駄だし...
f(a,b,c,n)=Σni=0⌊ai+bc⌋g(a,b,c,n)=Σni=0 i⌊ai+bc⌋h(a,b,c,n)=Σni=0⌊ai+bc⌋2 m=⌊an+bc⌋
fを押す
a>=cまたはb>=cの場合、f(a,b,c,n)=(a/c)∗n∗(n+1)/2+(b/c)∗(n+1)+f(a%c,b%c,c,n)が容易に得られる.f(a,b,c,n)=Σni=0Σmj=1[(ai+b)/c>=j]という式は幾何学的に理解できる.fの式の意味は、実際には、x=0とx=nの2本の鉛直線からなる直角台形内の整点数(縦座標が0の点を含まず、オンライン上の点を含む)である.次に私たちのこの式は1本の縦線を列挙して、上の整点の個数を統計して、私たちは今1本の横線を列挙して、横線の上の整点の個数を統計して、この式です.f(a,b,c,n)=Σni=0Σm−1 j=0[(ai+ b)/c>=j+1]f(a,b,c,n)=Σni= 0Σm−1 j=0[ai>= cj+c−b]f(a,b,c,n)=Σni= 0Σm−1 j=0[ai> cj+c−b−b−1 j=0[ai> cj+c−b−b−1]f(a,b,c,n)=Σni= 0Σm−1 j=0[i>(cj+c−b−b−b−1)/aa/a(a,b(a,b,n)=0Σni= 0Σm−1 j=0Σm]f(a,b,c,n)=Σmj=0(n−(cj+c−b−1)/a)f(a,b,c,n)=nm−f(c,c−b−1,a,m−1)は再帰処理を継続する.第1および第3次元表現状態のみを見ると,(a,c)から(c,a%c)になるたびに複雑度はユークリッドアルゴリズムと一致することが分かった.
gを押す
a>=cまたはb>=cの場合、g(a,b,c,n)=(a/c)∗n∗(n+1)∗(2 n+1)/6+(b/c)∗n∗(n+1)/2+g(a%c,b%c,c,n)が得られやすい.まずまずfと同じように下取りを変えてg(a,b,c,n)=Σni=0 iΣmj=1[(ai+ b)/c>=j]g(a,b,c,n)=Σni= 0 iΣm−1 j=0[i>(cj+c−b−b−1)/a]g(a,b,c,n)=1/2∗Σm−1−1 j=0(n+1+(cj+c−b−1)/a)n−(n−(cj+c−c−b−b−b−b)−b(b−(cj+c−c−b−b−b−b−b−b)−b(c−b−b−b−b−b)−b(c−1)/a)ここで見るのは少しつらいが,fのときに転化するのは実は0次方和であり,gは1次方和であり,だからここでは求和式を使いました.g(a,b,c,n)=1/2∗Σm−1 j=0 n(n+1)−(cj+c−b−1)/a−[(cj+c−b−1)/a]2 g(a,b,c,n)=1/2∗[n(n+1)m−f(c,c−b−1,a,m−1)−h(c,c−b−b−1,a,a,m−1)−b−1,a,m−1)]が取り外されたのはgが面倒なようで、hを押す必要がある.
プッシュh
a>=cまたはb>=cの場合、hも面倒なのですが・・・三項式の二乗は、多分こんなh(a,b,c,n)=(a/c)2∗n(n+1)(2 n+1)/6+(b/c)2∗(n+1)+(a/c)∗(b/c)∗n(n+1)+h(a%c,b%c,b%c,c,c,c,c)+2∗(a%c,b%c,c,+2)+2∗g(a%c,b%c,c,+n)+2)+2∗(a%c,+2)+2(a%c,+2,+c,∗(b/c)∗f(a%c,b%c,c,n)次にaとbがcより小さい場合、考え方を変えましょう.どのようにしてn^2を手に入れますか?n 2=2∗n(n+1)2−n=2Σni=0 i−nと考えられるh(a,b,c,n)=Σni=0(2∗Σ(ai+b)/cj=1 j−(ai+b)/c)を押すと交換主体が考えられる.h(a,b,c,n)=2∗∑m−1j=0(j+1)∗∑ni=0[(ai+b)/c>=j+1]−f(a,b,c,n) h(a,b,c,n)=2∗∑m−1j=0(j+1)∗∑ni=0[i>(cj+c−b−1)/a]−f(a,b,c,n) h(a,b,c,n)=2∗∑m−1j=0(j+1)∗(n−(cj+c−b−1)/a)−f(a,b,c,n) h(a,b,c,n)=nm(m+1)−2g(c,c−b−1,a,m−1)−2f(c,c−b−1,a,m−1)−f(a,b,c,n)
インプリメンテーション
私の実装はf,g,hのそれぞれの値を直接返すのが簡単です.境界はaが0で、3つの0を返します.upd:境界を書き間違えたようですから、みんなで押してください.ブスだし、強制変換しても無駄だし...
dong likegcd(ll a,ll b,ll c,ll n){
if (!a){
gjx.f=gjx.g=gjx.h=0;
return gjx;
}
if (a>=c||b>=c){
zlt=likegcd(a%c,b%c,c,n);
gjx.f=((ll)(a/c)*n%mo*(n+1)%mo*ni2%mo+(ll)(b/c)*(n+1)%mo)%mo;
(gjx.f+=zlt.f)%=mo;
gjx.g=((ll)(a/c)*n%mo*(n+1)%mo*(2*n+1)%mo*ni6%mo+(ll)(b/c)*(n+1)%mo*n%mo*ni2%mo)%mo;
(gjx.g+=zlt.g)%=mo;
gjx.h=(ll)(a/c)*(a/c)%mo*n%mo*(n+1)%mo*(2*n+1)%mo*ni6%mo;
(gjx.h+=(ll)(b/c)*(b/c)%mo*(n+1)%mo)%=mo;
(gjx.h+=(ll)(a/c)*(b/c)%mo*n%mo*(n+1)%mo)%=mo;
(gjx.h+=(ll)2*(a/c)%mo*zlt.g%mo)%=mo;
(gjx.h+=(ll)2*(b/c)%mo*zlt.f%mo)%=mo;
(gjx.h+=zlt.h)%=mo;
return gjx;
}
ll m=((ll)a*n+(ll)b)/(ll)c;
zlt=likegcd(c,c-b-1,a,m-1);
gjx.f=((ll)n*m%mo-(ll)zlt.f)%mo;
gjx.g=((ll)(n+1)*n%mo*m%mo-(ll)zlt.f-(ll)zlt.h)%mo;
gjx.g=(ll)gjx.g*ni2%mo;
gjx.h=((ll)n*m%mo*(m+1)%mo-(ll)2*zlt.g%mo-(ll)2*zlt.f%mo-(ll)gjx.f)%mo;
return gjx;
}