two reminder

2 secs 1024 MB
YSatUT's icon YSatUT
Tweet
問題
提出
テストケース
解説

l1≤q1≤r1,l2≤q2≤r2l_1\leq q_1\leq r_1,l_2\leq q_2\leq r_2とします。整数nnをm1m_1で割った余りがq1q_1、m2m_2で割った余りがq2q_2である時、整数p1,p2p_1,p_2を用いて、n=p1m1+q1=p2m2+q2n=p_1m_1+q_1=p_2m_2+q_2と表せます。この時、p1m1−p2m2=q2−q1p_1m_1-p_2m_2=q_2-q_1となります。

ここで、m1,m2m_1,m_2の最大公約数をggとし、m1=gm1′,m2=gm2′m_1=gm_1',m_2=gm_2'とします。この時、g(p1m1′−p2m2′)=q2−q1g(p_1m_1'-p_2m_2')=q_2-q_1となるので、q2−q1q_2-q_1がggの倍数でない場合、これを満たす(p1,p2)(p_1,p_2)の組は存在しません。

q2−q1q_2-q_1がggの倍数である時、q2−q1=kgq_2-q_1=kg（kkは整数）とおけるので、p1m1′−p2m2′=kp_1m_1'-p_2m_2'=kとなります。m1′,m2′m_1',m_2'は互いに素なので、これを満たす(p1,p2)(p_1,p_2)の組は必ず存在します。そのうちの1つを(s1,s2)(s_1,s_2)とすると、s1m1′−s2m2′=ks_1m_1'-s_2m_2'=kとなるので、m1′(p1−s1)=m2′(p2−s2)m_1'(p_1-s_1)=m_2'(p_2-s_2)となります。m1′,m2′m_1',m_2'は互いに素なので、p1−s1=m2′k′p_1-s_1=m_2'k'（k′k'は整数）となります。よって、p1=m2′k′+s1p_1=m_2'k'+s_1より、n=m1m2′k′+m1s1+q1=m1m2gk′+m1s1+q1n=m_1m_2'k'+m_1s_1+q_1=\frac{m_1m_2}{g}k'+m_1s_1+q_1となります。よって、(q1,q2)(q_1,q_2)の値を固定した場合、条件を満たすnnの周期はm1m2g\frac{m_1m_2}{g}となるので、0≤n<m1m20\leq n<m_1m_2の範囲に条件を満たすnnはgg個存在します。

よって、q2−q1q_2-q_1がggの倍数となるような(q1,q2)(q_1,q_2)の組の数をnq1,q2n_{q_1,q_2}とすると、求める答えはgnq1,q2gn_{q_1,q_2}です。

nq1,q2n_{q_1,q_2}の求め方

0≤i<g0\leq i<gとし、l1≤q1≤r1l_1\leq q_1\leq r_1内において、ggで割った余りがiiとなるようなq1q_1の数をA1,iA_{1,i}とします。また、l2≤q2≤r2l_2\leq q_2\leq r_2内において、ggで割った余りがiiとなるようなq2q_2の数をA2,iA_{2,i}とします。この時、nq1,q2=A1,0A2,0+A1,1A2,1+⋯+A1,g−1A2,g−1n_{q_1,q_2}=A_{1,0}A_{2,0}+A_{1,1}A_{2,1}+\cdots+A_{1,g-1}A_{2,g-1}となります。

ここで、A1,iA_{1,i}の値について考えてみます。ggの倍数の中で、l1l_1より大きい物の中で最小の物をl1′l_1'、r1r_1以下で最大の物をr1′r_1'とします。この時、t=r1′−l1′gt=\frac{r_1'-l_1'}{g}とすると、l1′≤q1≤r1′−1l_1'\leq q_1\leq r_1'-1にはggで割った余りが0,1,⋯ ,g−10,1,\cdots,g-1の物がtt個ずつ含まれています。また、l1,r1l_1,r_1をggで割った余りをそれぞれl1′′,r1′′l_1'',r_1''とすると、l1≤q1≤l1′−1l_1\leq q_1\leq l_1'-1にはggで割った余りがl1′′,l1′′+1,⋯ ,g−1l_1'',l_1''+1,\cdots,g-1の物が11個ずつ含まれており、またr1′≤q1≤r1r_1'\leq q_1\leq r_1にはggで割った余りが0,1,⋯ ,r1′′0,1,\cdots,r_1''の物が11個ずつ含まれています。よって、A1,iA_{1,i}の値は、

l1′′≤r1′′l_1''\leq r_1''の場合、A1,i={t+1if0≤i≤l1′′−1t+2ifl1′′≤i≤r1′′t+1ifr1′′+1≤i≤g−1A_{1,i}=\left\{\begin{array}{llc} t+1 & {\rm if} & 0\leq i\leq l_1''-1 \\ t+2 & {\rm if} & l_1''\leq i\leq r_1'' \\ t+1 & {\rm if} & r_1''+1\leq i\leq g-1 \end{array}\right.

l1′′=r1′′+1l_1''=r_1''+1の場合、A1,i=t+1A_{1,i}=t+1

l1′′≥r1′′+2l_1''\geq r_1''+2の場合、A1,i={t+1if0≤i≤r1′′tifr1′′+1≤i≤l1′′−1t+1ifl1′′≤i≤g−1A_{1,i}=\left\{\begin{array}{llc} t+1 & {\rm if} & 0\leq i\leq r_1'' \\ t & {\rm if} & r_1''+1\leq i\leq l_1''-1 \\ t+1 & {\rm if} & l_1''\leq i\leq g-1 \end{array}\right.

となります。なお、以下の図を見るとイメージしやすいです。

l1′′≤r1′′l_1''\leq r_1''の場合

i mod gi\ {\rm mod}\ g00⋯\cdotsl1′′l_1''⋯\cdotsr1′′r_1''⋯\cdotsg−1g-1
l1≤q1≤l1′−1l_1\leq q_1\leq l_1'-1○⋯\cdots⋯\cdots⋯\cdots○
r1′≤q1≤r1r_1'\leq q_1\leq r_1○⋯\cdots⋯\cdots⋯\cdots○

l1′′=r1′′+1l_1''=r_1''+1の場合

i mod gi\ {\rm mod}\ g00⋯\cdotsr1′′r_1''l1′′l_1''⋯\cdotsg−1g-1
l1≤q1≤l1′−1l_1\leq q_1\leq l_1'-1○⋯\cdots○
r1′≤q1≤r1r_1'\leq q_1\leq r_1○⋯\cdots○

l1′′≥r1′′+2l_1''\geq r_1''+2の場合

i mod gi\ {\rm mod}\ g00⋯\cdotsr1′′r_1''⋯\cdotsl1′′l_1''⋯\cdotsg−1g-1
l1≤q1≤l1′−1l_1\leq q_1\leq l_1'-1○⋯\cdots○
r1′≤q1≤r1r_1'\leq q_1\leq r_1○⋯\cdots○

いずれの場合についても、iiを00からg−1g-1まで増やした時のA1,iA_{1,i}の値の変化は高々2回となります。A2,iA_{2,i}についても同様に考えることで、値の変化は高々2回となります。よって、区間[0,g−1][0,g-1]をA1,i,A2,iA_{1,i},A_{2,i}の変化点で区切っても、区切りは高々4つなので、区間は高々5分割となります。よって、それぞれの区間に対してA1,iA2,iA_{1,i}A_{2,i}の値を求めれば良いです。

以上より、nq1,q2n_{q_1,q_2}の計算はO(1)O(1)で行えるので、プログラム全体の計算量はO(log⁡min⁡(a,b))O(\log\min(a,b))となります。

解答例は以下の通りです。

ans.cpp

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378