比赛链接：Dashboard - 2024.3.3 周赛 - Codeforces

C

题意：给出$p$，求整数对 $(a,b)$ 使得 $\frac{a}{b}=p$ 且 $\frac{a}{b},\frac{a+1}{b+1},\frac{a+2}{b+2}$ 均为整数。$p\leq10^{18}$

通过数学化简后即为求满足以下条件的 $b$ ：$k\times(b+1)\times(b+2)=2\times(p-1),b+1|p-1$

关于求 $a\times b\times f(b)=p,p\leq10^{18}$ 时，可采用如下的方法：

  1. 枚举 $a\in[1,\sqrt[3]p]$，使 $a$ 成为最小的值，然后手算出 $b$ 的值并判断是否满足条件。
  2. 枚举 $b\in[1,\sqrt[3]p]$， 使 $b$ 成为最小的值，然后判断 $a$ 是否满足条件。

这种方法可以使时间复杂度为 $O(\sqrt[3]p)$。

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
# include <bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;
LL p;

void solve()
{
	vector<LL>ans;
	int res = 0;
	cin >> p;
	p = 2*(p -1);
	
	for(LL k = 1; k * k<= 9 * p / k; k ++)
	{
		if(p % k == 0)
		{
			LL t = p / k;
			
			LL l = 1, r = t;
			while(l < r)
			{
				LL mid = l + r + 1 >> 1;
				if((mid + 1) > t / (mid + 2)) r = mid - 1;
				else l = mid;
			}
			
			if( (r + 1) * (r + 2) == t)  
			{
				LL b = r ;
				if(p % (2 * b + 2)== 0) ans.push_back(b);
			}
			
		}
	}

	for(LL b = 1; (b + 1) * (b + 1) <= 9 * p / (b + 1); b ++)
	{
		LL s = (b + 1) * (b + 2);
		if(p % s == 0 && p % (2 * b + 2) == 0) ans.push_back(b);
	}
	
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	cout << ans.size() << '\n';
	if(!ans.empty())
	{
		for(auto c : ans) cout << c << ' ';
		cout << '\n';
	}
	
}

int main()
{
    ios::sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while(T -- )solve();
    //system("pause"); 
    return 0;
}

math