Znzryb's Blog
0%

ABC-397-D - Cubes

Posted on Edited on

思路讲解

给你一个正整数N。判断是否存在一对正整数(x,y)，使得x3−y3=N.如果存在这样的一对，请打印这样的一对(x,y)。给你一个正整数 N 。判断是否存在一对正整数 (x,y) ，使得 x^3 - y^3 = N .\\如果存在这样的一对，请打印这样的一对 (x,y) 。

这个形式还是很简单的，但是字少，可能还是比较难的。这其实也算是一个丢番图方程。

根据数理逻辑，非线形丢番图方程一般无法直接求解，所以基本靠枚举去解。

image

暴力枚举d即可，d的上界是N1/3N^{1/3}，1e6，是可以解决的。

然后这道题目上界比较大

AC代码

https://atcoder.jp/contests/abc397/submissions/64414819

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
84
85
86
87
88
89
// Problem: D - Cubes
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
typedef __int128 i128;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

void print(i128 x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

inline void solve(){
	cin>>N;
	ll upD=ceil(pow((long double)N,(double)1/3));
// #ifdef LOCAL
    // cerr << upD << '\n';
// #endif
	// 枚举d
	for(__int128 d=1;d<=upD;++d){
		// 判断在这个d的条件下，y是不是合法的（是正整数吗？）
		__int128 delta=-3*d*d*d*d+12*d*N;
		if(delta<0) continue;
		i128 sqrtDel=sqrt(delta);
		if(sqrtDel*sqrtDel==delta){	// 验证delta为平方数
			i128 y=(-3*d*d+sqrtDel)/(6*d);
			if(y<=0) continue;
			if(y*6*d==(-3*d*d+sqrtDel)){	// 验证整除
				print(y+d);
				putchar(' ');
				print(y);
				return;
			}
		}
// #ifdef LOCAL
    // if(d==276544){
		// cerr<<"OK"<<"\n";
	// }
// #endif
		
	}
	cout<<-1<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc397/submissions/64414819
*/

心路历程（WA，TLE，MLE……）

1
ceil(pow((long double)N,(double)1/3));

小心C++隐式类型转换