Iksevi 题解

TKXZ133's Blog / 2023-09-05 / 原文

Iksevi

题目大意

$n$ 次询问，每次给定一个点 $(x,y),x\ge 0, y\ge 0$，问有多少种对角线长为偶数的正方形使得在用该正方形正密铺第一象限的情况下该点位于正方形顶点上。

正密铺第一象限 指将第一个正方形的角与 $x$ 轴和 $y$ 轴接触。此后的正方形都与至少一个已放置的正方形有一条边重合。重复这一过程。

思路分析

考虑到 $x,y$ 对称，因此不妨设 $y>x$。

设当前考虑的正方形对角线长为 $2l$，那么容易发现该正方形合法的充要条件是：

\[\begin{cases}y+x\equiv l\pmod {2l}\\y-x\equiv l\pmod {2l}\end{cases} \]

将两式相加，得：

\[y\equiv0\pmod {2l} \]

因此我们只需要枚举 $y$ 的所有约数，再逐一判断就可以做到 $O(n\sqrt V)$ 的时间复杂度，可以取得 $70pts$ 的好成绩。

但我们发现 $10^7$ 内约数个数最多的数只有 $448$ 个约数，因此 $O(\sqrt V)$ 的枚举是相当浪费的。

考虑将询问离线并离散化，改为枚举 $1\sim V$ 的倍数，对所有的询问点开 vector 并加入约数，这样我们的时间复杂度就优化（~~或许是劣化~~）成了 $O(V\ln V+n\log n+n\max \{d\})$，空间复杂度为 $O(V+n\max\{d\})$，其中 $\max\{d\}=448$，可以通过。

代码

（最大时间 $2.71s$，最大空间 $171.27MB$）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
const int N = 1100000, M = 10000010, L = 10000000;

int n, A, D, in1, in2;
int b[N], id[M];

struct Node{
    int x, y;
}a[N];

vector <int> d[N];

bool check(int k){
	return A % (2 * k) == k && D % (2 * k) == k;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d", &in1, &in2);
        if (in1 < in2) swap(in1, in2);
        a[i] = Node{in1, in2};
        b[i] = in1; id[in1] = 1;
    }
    sort(b + 1, b + n + 1);
    int tot = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= L; i ++)
        if (id[i]) id[i] = lower_bound(b + 1, b + n + 1, i) - b;
    for (int i = 1; i <= L; i ++)
        for (int j = i; j <= L; j += i)
            if (id[j]) d[id[j]].push_back(i);
    for (int i = 1; i <= n; i ++) {
        int ans = 0;
        A = a[i].x + a[i].y ;
        D = abs(a[i].x - a[i].y);
		for (auto it : d[id[a[i].x]])
            if (check(it)) ans ++;
        cout << ans << '\n';
    }
    return 0;
}