均摊+推简单数论：ICPC2025沈阳A

image-20261008212715398

Square Kingdom - Problem - QOJ.ac

令 i>ji>j，考虑

(i+ba)2−(j+ba)2=(i−j)(i+j+2ba)=(i−j)(ai+aj+2b)a\begin{align*}\left(i+\dfrac b a\right)^2-\left(j+\dfrac b a\right)^2 &= (i-j)\left(i+j+\dfrac {2b}a\right)\\ &=\dfrac{(i-j)(ai+aj+2b)}{a} \end{align*}

因此我们可以考虑二分 DD，然后判断有多少个满足的点对。

考虑枚举 d=i−jd=i-j，通过推式子可以得到 ii 的范围：

i≤D+ad2−2bd2adi \le \dfrac{D+ad^2-2bd}{2ad}

同时满足 i∈[d+1,n]i\in[d+1,n]，这样子可以求出多少个合法 ii。

而 dd 枚举的上界不超过 2k\sqrt{2k}，因为若 (i,j)(i,j) 合法，则必有 j≤j′≤i′≤ij\le j'\le i'\le i 的 (i′,j′)(i',j') 合法。

时间复杂度 O(klog⁡(na))O(\sqrt{k}\log (na))

赛时失误：

  1. 一开始直接在没合并前就把 aa 提出来，导致分析过程中分母是 a2a^2
  2. 采用的是枚举 ii 推 dd，那样子要解一个二次方程。没有考虑过反过来有均摊的性质
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#include<cassert>
using namespace std;bool Mbe;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
//#define N
int n, m, i, j, k, T;
__int128 a, b, M; 

__int128 gcd(__int128 x, __int128 y) {
	while(y) {
		__int128 z = x % y; 
		x = y; y = z; 
	}
	return x; 
}

void write(__int128 x) {
	if(x / 10 > 0) write(x / 10); 
	putchar(x % 10 + '0'); 
}

__int128 min(__int128 x, __int128 y) {
	return (x < y) ? x : y; 
}

bool check(__int128 D) {
	__int128 cnt = 0, d; 
	for(d = 1; d <= min(M, n - 1); ++d) {
		__int128 k = (D + a * d * d - 2 * b * d) / (2 * a * d); 
		if(k > n) k = n; k -= d; 
		if(k <= 0) continue; 
		cnt += k; 
//		debug("To Big than %lld : For %lld, it need %lld [%lld]\n", (int)D, (int)d, (int)k, (int)cnt); 
//		debug("For ")
		if(cnt >= m) return true; 
	}
	return false; 
}

bool Med; signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	  atexit([]{fprintf(stderr,"%.lfms\n%lfMB\n",clock()*1000./CLOCKS_PER_SEC,(&Mbe-&Med)/1024./1024);});
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); m = read(); a = read(); b = read(); 
	M = 2 * sqrt(m) + 5; 
	__int128 l = 1, r = 1; 
	for(i = 1; i <= 30; ++i) r = r * 10; 
	while(l < r) {
		__int128 mid = (l + r) >> 1; 
		if(check(mid)) r = mid; 
		else l = mid + 1; 
	}
	__int128 x = gcd(l, (__int128)a); 
	l /= x; a /= x; 
	write(l); putchar(' '); write(a); 
	return 0;
}