发布时间：2024-07-31

类欧几里得

$ f(a,b,c,n)=\sum_{i=0}^N \lfloor \frac{a \cdot i+b}{c} \rfloor $
$ = \sum_{i=0}^N \frac{(\lfloor \frac{a}{c} \rfloor \cdot c+a\mod c)i+ \lfloor \frac{b}{c} \rfloor \cdot c+b \mod c}{c} $
$ =\frac{n+1}{2} \lfloor \frac{a}{c} \rfloor + (n+1) \lfloor \frac{b}{c} \rfloor + \sum_{i=0}^N \lfloor \frac{(a \mod c) \cdot i+b \mod c}{c} \rfloor $
$ =\frac{n+1}{2} \lfloor \frac{a}{c} \rfloor + (n+1) \lfloor \frac{b}{c} \rfloor +f(a \mod c,b \mod c,c,n) $

如下 $ f为 \sum_{i=0}^N \lfloor \frac{ai+b}{c} \rfloor ,g为\sum_{i=0}^N \lfloor \frac{ai+b}{c} \rfloor^2,h为 \sum_{i=0}^N i \lfloor \frac{ai+b}{c} \rfloor $

cpp

#include <cstdio>
using namespace std;
constexpr long long P = 998244353;
long long i2 = 499122177, i6 = 166374059;

struct data_t {
  data_t() { f = g = h = 0; }

  long long f, g, h;
};  // 三个函数打包

data_t calc(long long n, long long a, long long b, long long c) {
  long long ac = a / c, bc = b / c, m = (a * n + b) / c, n1 = n + 1,
            n21 = n * 2 + 1;
  data_t d;
  if (a == 0) {  // 迭代到最底层
    d.f = bc * n1 % P;
    d.g = bc * n % P * n1 % P * i2 % P;
    d.h = bc * bc % P * n1 % P;
    return d;
  }
  if (a >= c || b >= c) {  // 取模
    d.f = n * n1 % P * i2 % P * ac % P + bc * n1 % P;
    d.g = ac * n % P * n1 % P * n21 % P * i6 % P + bc * n % P * n1 % P * i2 % P;
    d.h = ac * ac % P * n % P * n1 % P * n21 % P * i6 % P +
          bc * bc % P * n1 % P + ac * bc % P * n % P * n1 % P;
    d.f %= P, d.g %= P, d.h %= P;

    data_t e = calc(n, a % c, b % c, c);  // 迭代

    d.h += e.h + 2 * bc % P * e.f % P + 2 * ac % P * e.g % P;
    d.g += e.g, d.f += e.f;
    d.f %= P, d.g %= P, d.h %= P;
    return d;
  }
  data_t e = calc(m - 1, c, c - b - 1, a);
  d.f = n * m % P - e.f, d.f = (d.f % P + P) % P;
  d.g = m * n % P * n1 % P - e.h - e.f, d.g = (d.g * i2 % P + P) % P;
  d.h = n * m % P * (m + 1) % P - 2 * e.g - 2 * e.f - d.f;
  d.h = (d.h % P + P) % P;
  return d;
}

long long T, n, a, b, c;

signed main() {
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
    data_t ans = calc(n, a, b, c);
    printf("%lld %lld %lld\n", ans.f, ans.h, ans.g);
  }
  return 0;
}

类欧几里得 ​

类欧几里得