ABC448E-Simple-Division

题意大意

给定游程编码表示的整数 $N$ 和整数 $M$，游标编码即由 $K$ 组 $(c_i, l_i)$ 描述，表示数字 $c_i$ 重复 $l_i$ 次，求 $\left\lfloor \frac{N}{M} \right\rfloor \bmod 10007$。
由于 $l_i$ 可达 $10^9$，所以无法直接构造 $N$。

解题思路

维护 $N \bmod (M \times 10007)$。设 $\text{Mod} = M \times 10007$，则答案为 $\frac{N \bmod \text{Mod}}{M} \bmod 10007$ 。

为什么模数是 $M \times 10007$？

题目要求的是商 $Q = \lfloor N/M \rfloor$ 对 $10007$ 取模的结果。

• 若只对 $M$ 取模，只能得到余数，商的信息完全丢失。
• 若只对 $10007$ 取模，由于中间过程涉及整除，模运算性质不直接适用。

为了方便，我们设 $P = 10007$，我们维护 $R = N \bmod (M \times P)$。
根据带余除法，存在整数 $k$ 使得 $N = k \cdot (M \cdot P) + R$。
两边同时除以 $M$ 并向下取整：

$$\lfloor \frac{N}{M} \rfloor = k \cdot P + \lfloor \frac{R}{M} \rfloor$$

对上式取模 $P$：

$$\lfloor \frac{N}{M} \rfloor \bmod P = (k \cdot P + \lfloor \frac{R}{M} \rfloor) \bmod P = \lfloor \frac{R}{M} \rfloor \bmod P$$

因为 $0 \le R < M \times P$，所以 $0 \le \lfloor \frac{R}{M} \rfloor < P$。
这意味着 $\lfloor \frac{R}{M} \rfloor$ 本身就是小于 $P$ 的非负整数，直接等于它模 $P$ 的结果。

结论：只要算出 $N \bmod (M \times 10007)$，将其除以 $M$ 取整，即为答案。直接计算需除以 9，但 $M$ 可能含因数 3，导致模逆元不存在。解决方法：

1. 计算 $r = 10^y \bmod (9 \times \text{Mod})$。
2. 由于 $10^y \equiv 1 \pmod{9}$，$r-1$ 必能被 9 整除，故 $\frac{r-1}{9}$ 为整数。

每段数字 $x$ 重复 $y$ 次的数值可表示为：

$$x \times \frac{10^y - 1}{9}$$

状态更新公式

维护当前余数 $\text{ans}$：

$$\text{ans} = (\text{ans} \times r + x \times \frac{r-1}{9}) \bmod \text{Mod}$$

其中 $r = 10^y \bmod (9 \times \text{Mod})$。

Code

---

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,m,ans,Mod;
ll qpow(ll a,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    cin>>T>>m;
    Mod=m*10007;
    while(T--){
        ll x,y;
        cin>>x>>y;
        ll r=qpow(10,y,Mod*9);
        ans=(ans*r%Mod+x*(r-1)/9)%Mod;
    }
    cout<<(ans/m)%10007;
    return 0;
}