test/math/divisor/aoj_1626.test.cpp

• View this file on GitHub
• Last update: 2023-11-13 04:31:16+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/1626

Depends on

• 約数列挙 (src/math/divisor.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1626

#include "src/math/divisor.hpp"

#include <iostream>

using namespace std;

int main() {
	int b;
	while (cin >> b, b) {
		int bottom = b, num = 1;
		for (auto v : divisor(2 * b)) {
			int tmp = (2 * b / v - v + 1);
			if (tmp <= 0 || tmp & 1) continue;
			bottom = tmp / 2;
			num = v;
		}
		cout << bottom << " " << num << endl;
	}

	return 0;
}

#line 1 "test/math/divisor/aoj_1626.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1626

#line 1 "src/math/divisor.hpp"



#include <algorithm>
#include <vector>

template<class T>
std::vector<T> divisor(T n) {
	std::vector<T> res;
	for (T i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			res.push_back(i);
			if (i * i != n) res.push_back(n / i);
		}
	}
	std::sort(res.begin(), res.end());
	return res;
}


#line 4 "test/math/divisor/aoj_1626.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int b;
	while (cin >> b, b) {
		int bottom = b, num = 1;
		for (auto v : divisor(2 * b)) {
			int tmp = (2 * b / v - v + 1);
			if (tmp <= 0 || tmp & 1) continue;
			bottom = tmp / 2;
			num = v;
		}
		cout << bottom << " " << num << endl;
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	217 ms	7 MB
g++	testcase_01	AC	45 ms	8 MB
clang++	testcase_00	AC	64 ms	8 MB
clang++	testcase_01	AC	67 ms	14 MB

Back to top page