竞赛讨论区 > 迟迟迟迟到的题解:200C 计算几何
头像
_rqy
发布于 2018-10-19 11:04
+ 关注

迟迟迟迟到的题解:200C 计算几何

Description
给定 a, b, c, d ,求有多少组 平面向量对使得 ,且 的横纵坐标都是整数。

Solution
考虑向量的复数表示: 。简单地计算可以说明
所以要求 的方案数,实际上就是要求有几对“复整数”的乘积是,也就是后者在“复整数”意义下的“因数个数”。
可以类比正整数定义“复整数”上的“整除”,也就是说如果uv=w,那么就说w被u整除(其中u,v,w都是复整数)、“复素数”,也就是说如果u的因数只有u,-u,iu,-iu,1,-1,i,-i这八个(显然这八个必定整除u),他就是复素数;同样的可以定义“互质”以及“积性函数”;并且同样的可以对“因数个数”进行“线性筛”,也就是对一定范围内的复整数以O(元素个数)的复杂度计算其每个数的因数个数。
例如,,而都是“复素数”,所以4的约数个数就是(2+1)x(2+1)=9(因数个数显然可以像整数意义下,把每个质因数的指数加一再相乘)。
且慢:正整数有一个顺序关系,使得前面的数乘一乘会变成后面的数,我们才能按这个顺序来线性筛。那复整数呢?
显然两个复整数的乘积模长等于其模长的乘积,所以按模长排序计算即可。同样的我们不能只计算[-1000,1000]x[-1000,1000]矩形内的答案,而要求半径为的圆内的答案。
但是rqy似乎算错了暴力复杂度....暴力枚举两个模长乘积不超过的复数似乎也是O(n2)的...
Std Code
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>


char getChar() {
  const int L = 10000000;
  static char buf[L], *p = buf, *end = buf;
  if (p == end) {
    if (feof(stdin)) return -1;
    end = buf + fread(p = buf, 1, L, stdin);
  }
  return *(p++);
}

int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getChar()))
    if (c == '-') f = -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getChar()));
  return ans * f;
}

inline int abs(int x) { return x < 0 ? -x : x; }

const int N = 1050;
const int M = (int)(1.5 * N);

struct NComp {
  int r, i;
  // (a + bi) * {1, -1, i, -i}
  // a > 0, b >= 0 OR a = b = 0
  NComp(int x = 0, int y = 0) {
    // x + yi; -y+xi; -x-yi; y-xi
    if (x == 0 || x * y < 0) std::swap(x, y);
    r = abs(x);
    i = abs(y);
  }

  inline friend int Abs(const NComp &x) {
    return x.r * x.r + x.i * x.i;
  }

  inline friend bool operator<(const NComp &a, const NComp &b) {
    int la = Abs(a), lb = Abs(b);
    return la == lb ? a.r < b.r : la < lb;
  }

  inline friend bool operator==(const NComp &a, const NComp &b) {
    return a.r == b.r && a.i == b.i;
  }

  inline friend NComp operator*(const NComp &a, const NComp &b) {
    return NComp(a.r * b.r - a.i * b.i, a.r * b.i + b.r * a.i);
  }
};

NComp T[M * M], Pr[M * M];
int minP[M][M], d[M][M], ld[M][M];
int S[N][N];

void Sieve(int n) {
  int K = n * n * 2, s = 0, pr_cnt = 0;
  d[1][0] = 1;
  for (int i = 1; i * i <= K; ++i)
    for (int j = 0, t = K - i * i; j * j <= t; ++j)
      T[s++] = NComp(i, j);
  std::sort(T, T + s);
  for (int i = 1; i < s; ++i) { // T[0] = 1+0i
  NComp x = T[i];
    if (!minP[x.r][x.i]) {
      Pr[minP[x.r][x.i] = ++pr_cnt] = x;
      ld[x.r][x.i] = 1;
      d[x.r][x.i] = 2;
    }
    int t = minP[x.r][x.i], q = d[x.r][x.i];
    for (int j = 1; j <= t; ++j) {
      NComp y = x * Pr[j];
      if (Abs(y) > K) break;
      minP[y.r][y.i] = j;
      ld[y.r][y.i] = q;
      d[y.r][y.i] = j == t ? q * 2 - ld[x.r][x.i] : q * 2;
    }
  }
  for (int i = 0; i <= n; ++i) {
    S[0][i] = 0;
    S[i][0] = (i ? S[i - 1][0] : 0) + d[i][0];
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + d[i][j];
}

int get(int a, int b) {
  if (a >= 0) {
    if (b >= 0) return S[a][b] - S[a][0];
    else return -S[a][-(b + 1)];
  } else {
    if (b >= 0) return -S[b][-(a + 1)];
    else return S[-(a + 1)][-(b + 1)] + S[-(b + 1)][0];
  }
}

int main() {
  Sieve(1000);
  int T = readInt();
  int ans = 0;
  while (T--) {
    int a = readInt() - 1, b = readInt(), c = readInt() - 1, d = readInt();
    ans ^= (get(b, d) - get(a, d) - get(b, c) + get(a, c));
    // printf("%d\n", (get(b, d) - get(a, d) - get(b, c) + get(a, c)) << 2);
  }
  printf("%d\n", ans << 2);
  return 0;
}
 

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐