题意解析 对于题目中的式子，我们有 ∑k=1Nkmod  M=N×(N+1)/2mod  M\sum_{k=1}^{N}k \mod M = N \times (N + 1) / 2 \mod M∑k=1N kmodM=N×(N+1)/2modM。 但是由于本题的 N(1≤N≤104×106)N (1 \le N \le 10^{4 \times 10^6})N(1≤N≤104×106) 非常大，直接计算上面的式子时间复杂度为 O(log⁡2N)\mathrm{\mathrm{O}}(\log^2{N})O(log2N)，计算量大概为 1.6×10131.6 \times 10^{13}1.6×1013，会超出时间限制。 我们考虑 1+2+3+⋯+2×M−1+2×M=M×(2×M+1)1 + 2 + 3 + \cdots + 2 \times M - 1 + 2 \times M = M \times (2 \times M + 1)1+2+3+⋯+2×M−1+2×M=M×(2×M+1)。 而 M×(2×M+1)∣MM \times (2 \times M + 1) \vert MM×(2×M+1)∣M，即每 2×M2 \times M2×M 个数字的和对 MMM 取余的值为 000。 令 K=Nmod  (M×2)K = N \mod (M \times 2)K=Nmod(M×2)，我们只需要计算最后的 KKK 个数字的和即可。 而最后的 KKK 个数字的形式为 i×M×2+1,i×M×2+2,i×M×2+3,⋯+i×M×2+Ki \times M \times 2 + 1, i \times M \times 2 + 2, i \times M \times 2 + 3, \cdots + i \times M \times 2 + Ki×M×2+1,i×M×2+2,i×M×2+3,⋯+i×M×2+K。 每个数字对 MMM 取余得到 1+2+3+⋯+K=K×(K+1)/21 + 2 + 3 + \cdots + K = K \times (K + 1) / 21+2+3+⋯+K=K×(K+1)/2。 对于本题 M(1≤M≤109),K(0≤K<M×2)M(1 \le M \le 10^9), K(0 \le K < M \times 2)M(1≤M≤109),K(0≤K<M×2)，可以直接做整形运算。 对于 NNN，令其长度为 nnn， 我们可以将其写成 ∑i=0na[i]×10i\sum_{i=0}^{n}a[i] \times 10^i∑i=0n a[i]×10i，其中 a[i]a[i]a[i] 为其从低位到高位上的数字。那么我们便可以从逐位处理求得 Nmod  (M×2)N \mod (M \times 2)Nmod(M×2)。 AC代码 复杂度分析 求 Nmod  (M×2)N \mod (M \times 2)Nmod(M×2) 的时间复杂度为 O(log⁡N)\mathrm{O}(\log{N})O(logN)； 计算 K×(K+1)/2mod  MK \times (K + 1) / 2 \mod MK×(K+1)/2modM。的时间复杂度为 O(1)\mathrm{O}(1)O(1)。