Submission #64571765

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
uint64_t add(uint64_t a, uint64_t b) {
  if (a > UINT64_MAX - b) return UINT64_MAX;
  return a + b;
}
uint64_t mul(uint64_t a, uint64_t b) {
  if (b == 0) return 0;
  if (a > UINT64_MAX / b) return UINT64_MAX;
  return a * b;
}
uint64_t N;
int buhin_cnt = 0;
uint64_t buhin[128];
int kosuu[128];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

uint64_t add(uint64_t a, uint64_t b) {
	if (a > UINT64_MAX - b) return UINT64_MAX;
	return a + b;
}

uint64_t mul(uint64_t a, uint64_t b) {
	if (b == 0) return 0;
	if (a > UINT64_MAX / b) return UINT64_MAX;
	return a * b;
}

uint64_t N;

int buhin_cnt = 0;
uint64_t buhin[128];
int kosuu[128];

void search(int pos, uint64_t cur) {
	if (pos >= buhin_cnt) {
		const uint64_t diff = cur, target = N / cur;
		uint64_t l = diff + 1, r = UINT64_MAX;
		while (l <= r) {
			uint64_t m = l + (r - l) / 2;
			uint64_t check = add(add(mul(m, m), mul(m, m - diff)), mul(m - diff, m - diff));
			if (check == target) {
				printf("%" PRIu64 " %" PRIu64 "\n", m, m - diff);
				exit(0);
			} else if (check < target) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
	} else {
		int i;
		search(pos + 1, cur);
		for (i = 0; i < kosuu[pos]; i++) {
			cur *= buhin[pos];
			search(pos + 1, cur);
		}
	}
}

int main(void) {
	uint64_t cur, i;
	if (scanf("%" SCNu64, &N) != 1) return 1;
	cur = N;
	for (i = 2; i * i <= cur; i++) {
		if (cur % i == 0) {
			buhin[buhin_cnt] = i;
			while (cur % i == 0) {
				kosuu[buhin_cnt]++;
				cur /= i;
			}
			buhin_cnt++;
		}
	}
	if (cur > 1) {
		buhin[buhin_cnt] = cur;
		kosuu[buhin_cnt] = 1;
		buhin_cnt++;
	}
	search(0, 1);
	puts("-1");
	return 0;
}

/*

[ 高校数学 ] x の3乗と y の3乗の和および差の因数分解は記憶すべし - 偏差値40プログラマー
https://hensa40.cutegirl.jp/archives/493

x^3 - y^3 = (x - y) * (x^2 + x*y + y^2)

前半を固定 → xを決めるとyも決まる、後半は単調増加 → 二分探索的な感じのやつ

*/

Submission Info

Judge Result