モノイド積版 Floor Sum を用いる解法で，MMNMMさんのユーザー解説 とは異なる方針です．

定式化をしておきます．

非負整数 \(a,b\) および正整数 \(m\) に対し \(f(n)=\left\lfloor\frac{an+b}{m}\right\rfloor\) とする． モノイド \(M\) の元 \(x,y\) および正整数に対し， \[y^{f(0)}xy^{f(1)-f(0)}x\cdots xy^{f(n)-f(n-1)}(=:z)\] を \(M\) の演算 \(O(\log a+\log b+\log n+\log m)\) 回で求めることができる．

モノイドおよびその元 \(x,y\) を適切に定めることが目標になります．

仮に \(X^{-1}\bmod R\) が存在するならば，以下のようにして解けます．

• 台集合：\(\mathbb{Z}\times(\mathbb{Z}/R\mathbb{Z})\)
• 演算：\((a_1,x_1)\cdot(a_2,x_2)=(a_1+a_2,x_1+X^{a_1}x_2)\)
• \(x=(A,1),y=(-M,0)\)
• 答えは \((B,0)\cdot z\) の第二成分

しかし一般には \(X\) の\({}\bmod R\) での逆元は存在せず，上の方法では \(X\) の指数に負数が来た場合に困ります．

そこで \(X\) のべきをなるべく括り出すようにして，以下のように定めます．

• 台集合：\(\mathbb{Z}\times\mathbb{Z}\times(\mathbb{Z}/R\mathbb{Z})\)
• 演算：\((a_1,b_1,x_1)\cdot(a_2,b_2,x_2)=(a_1+a_2,b,X^{b_1-b}x_1+X^{a_1+b_2-b}x_2)\)
  • ただし \(b:=\min(b_1,a_1+b_2)\) である
• \(x=(A,0,1),y=(-M,0,0)\)

すると \((B,0,0)\cdot z=(a,b,x)\) としたとき \(b=0\) であることが示せるため，\(x\) が求める答えになっています．