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) 回帖