关于取模、进制的问题

先来定义一下取模（b不等于0）。

\(r(a, b) = a - b \times \lfloor \frac{a}{b} \rfloor = t\)

下面讨论一下t的取值范围。

1. b>0

\(k=\lfloor \frac{a}{b} \rfloor\)，则 \(r(a,b)=a-kb\)。

因为 \(k \le \frac{a}{b} < k+1\)，\(a-b\times \frac{a}{b}=0\)。

配凑一下，就是 \(a-bk-b<a-b\times \frac{a}{b}=0\le a-bk\)

\(a-bk=r(a,b)\ge 0, a-bk=r(a,b)<b\)，所以 \(0 \le r(a,b) < b\)。

2. b<0，同理 \(b<r(a,b)\le 0\)。

接着我们尝试让情况二变成情况一的范围。

直觉告诉我们，不等式加上-b就可以了。

\(a=kb+r=r-b+b+kb=(k+1)b+(r-b)\)

此时 \(0<r(a,b)\le -b\)，这个等号很烦，干脆当\(r(a,b)=0\)时不变化，这样就ok了。

于是，r的取值范围就统一为了 \(0 \le r < |b|\)

另外C++里面商是负数的时候会向上取整，用类似的方法可以证明此时的余数是 \(-b<r\le 0\)，所以(r+mod)%mod，最后%mod就是防止\(r=0\)的情况，此时应该不修改r，刚好%mod可以做到这一点。

进制分解可以看成一个递归的过程

k进制

div(x)=k*div([x/k])+r(x,k)

[x/k]和上述证明一样，如果k是负数，就+1。

画成递归树会发现这样子构造的方案刚好满足进制的定义（\(k^n...\)）。

例题：P1017 [NOIP2000 提高组] 进制转换