AcWing 5068. 平方朋友对
原题链接
简单
作者:
卡冈图亚
,
2023-07-16 03:27:43
,
所有人可见
,
阅读 168
等式:(A + i) * 1000 + k == (B + i) * (B + i), 其中k >= 0 && k <= 999, i >= 0 && i < n
如果枚举A,需要维护一个B的集合判断B是否存在,时间复杂度$O(m(n+c))$, c为维护集合的时间,不可取
观察发现B有平方,开方后会小很多,因此考虑枚举B,同时改变不等式形式后发现枚举B时区间最多一个A
因为((B + i) * (B + i) - 999) / 1000 < A + i < (B + i) * (B + i) / 1000
左右两边分别向上向下取整后A = ((B + i) * (B + i) / 1000)向下取整 - i
因此枚举B时不需要维护集合,直接判断A出现次数即可,时间复杂度$O(n√1000m)$
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ri register int
#define endl '\n'
#define rep(i, x, y) for(ri i = x; i <= y; ++ i)
#define pre(i, x, y) for(ri i = x; i >= y; -- i)
#define x first
#define y second
#define lowbit(x) (x&(-x))
#define maxe max_element
#define mine min_element
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
using namespace std;
using i64 = int64_t;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k;
i64 cnt;
PII q[N];
int main()
{
IOS;
cin >> n >> m;
k = (m + n - 1) * 1000 + 999;
k = sqrt(k);
rep(i, 1, k)
{
bool flag = true;
ri pre = -1;
rep(j, 0, n - 1)
{
ri t = (i + j) * (i + j);
t = t / 1000 - j;
if(t < 0 || pre != -1 && t != pre)
{
flag = false;
break;
}
pre = t;
}
if(flag) q[++ cnt] = {pre, i};
}
if(!cnt) cout << "No Solution." << endl;
else
{
sort(q + 1, q + cnt + 1);
rep(i, 1, cnt) cout << q[i].x << ' ' << q[i].y << endl;
}
return 0;
}