#96244 (C++11) No.376 立方体のN等分 (2)

• 問題: No.376 立方体のN等分 (2)
• ユーザー: hanorver
• 提出日時: 2016-06-05 09:14:59
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,052 bytes
• コンパイル時間: 645 ms
• コンパイル使用メモリ: 68,104 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-08 14:55:01
• 合計ジャッジ時間: 8,310 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	WA	-
testcase_03	AC	238 ms; 5,248 KB
testcase_04	WA	-
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	9 ms; 5,248 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	145 ms; 5,248 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	105 ms; 5,248 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	122 ms; 5,248 KB
testcase_19	WA	-
testcase_20	AC	151 ms; 5,248 KB
testcase_21	WA	-
testcase_22	AC	132 ms; 5,248 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	138 ms; 5,248 KB
testcase_26	WA	-
testcase_27	AC	190 ms; 5,248 KB
testcase_28	AC	133 ms; 5,248 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	129 ms; 5,248 KB
testcase_32	AC	193 ms; 5,248 KB
testcase_33	AC	132 ms; 5,248 KB
testcase_34	AC	132 ms; 5,248 KB
testcase_35	AC	190 ms; 5,248 KB
testcase_36	AC	140 ms; 5,248 KB
testcase_37	AC	132 ms; 5,248 KB
testcase_38	AC	230 ms; 5,248 KB
testcase_39	WA	-

ソースコード

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

void factor(long long n, std::vector<long long> &v) {
	v.push_back(1);
	if (n % 2 == 0) {
		v.push_back(2);
		while (n % 2 == 0) n /= 2;
	}
	if (n % 3 == 0) {
		v.push_back(3);
		while (n % 3 == 0) n /= 3;
	}
	if (n % 5 == 0) {
		v.push_back(5);
		while (n % 5 == 0) n /= 5;
	}

	long long end = sqrt(n);
	for (long long i = 6; i <= end; i+=6) {
		if (n % (i - 1) == 0) {
			v.push_back(i - 1);
			while (n % (i - 1) == 0) n /= (i - 1);
		}
		if (n % (i + 1) == 0) {
			v.push_back(i + 1);
			while (n % (i + 1) == 0) n /= (i + 1);
		}
	}
}

int main() {
	long long n;

	std::cin >> n;

	long long max = n - 1, min = n - 1;

	long long a, b, c;

	std::vector<long long> v;

	factor(n, v);

	for (long long i : v) {
		if (i * i * i > n) break;
		if (n % i != 0) continue;
		long long tn = n / i;
		for (long long j = i; j * j <= tn; j++) {
			if (tn % j != 0) continue;
			min = std::min(min, i + j + tn / j - 3);
		}
	}

	std::cout << min << " " << max << std::endl;
	return 0;
}