#683170 (C++17) No.1626 三角形の構築

提出ソース

結果

問題	No.1626 三角形の構築
ユーザー	kwm_t
提出日時	2021-07-24 18:34:32
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	303 ms / 2,000 ms
コード長	4,734 bytes
コンパイル時間	2,889 ms
コンパイル使用メモリ	225,192 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-20 16:12:47
合計ジャッジ時間	4,523 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	4 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	5 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	5 ms 5,376 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	4 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	4 ms 5,376 KB
testcase_17	AC	4 ms 5,376 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	4 ms 5,376 KB
testcase_20	AC	5 ms 5,376 KB
testcase_21	AC	4 ms 5,376 KB
testcase_22	AC	6 ms 5,376 KB
testcase_23	AC	6 ms 5,376 KB
testcase_24	AC	77 ms 5,376 KB
testcase_25	AC	303 ms 5,376 KB
testcase_26	AC	18 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
//const bool debug = false;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using ull = unsigned long long;
long long cheker(long long n) {
	if (n < 0)return -1;
	for (long long i = max((double)0, sqrt(n) - 10); i <= sqrt(n) + 10; ++i) {
		if (i * i == n)return i;
	}
	return -1;
}
ll sq(ll n) {
	ll ng = -1, ok = 3 * 1e9;
	while (abs(ng - ok) > 1) {
		ll mid = (ok + ng) / 2;
		if (mid * mid >= n)ok = mid;
		else ng = mid;
	}
	if (ok * ok == n)return ok;
	else return -1;
}

struct Miller {
	const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
	// x^k (mod m)
	long long modpow(long long x, long long k, long long m) {
		long long res = 1;
		while (k) {
			if (k & 1) {
				res = res * x % m;
			}
			k /= 2;
			x = x * x % m;
		}
		return res;
	}
	// check if n is prime
	bool check(long long n) {
		if (n < 2) {
			return false;
		}
		long long d = n - 1;
		long long s = 0;
		while (d % 2 == 0) {
			d /= 2;
			s++;
		}
		for (long long a : v) {
			if (a == n) {
				return true;
			}
			if (modpow(a, d, n) != 1) {
				bool ok = true;
				for (long long r = 0; r < s; r++) {
					if (modpow(a, d * (1LL << r), n) == n - 1) {
						ok = false;
						break;
					}
				}
				if (ok) {
					return false;
				}
			}
		}
		return true;
	}
};

struct Rho {
	mt19937 mt;
	Miller miller;
	long long c;
	Rho() {
		mt.seed(clock());
	}
	inline long long f(long long x, long long n) {
		return (x * x + c) % n;
	}
	long long check(long long n) {
		if (n == 4) {
			return 2;
		}
		c = mt() % n;
		long long x = mt() % n;
		long long y = x;
		long long d = 1;
		while (d == 1) {
			x = f(x, n);
			y = f(f(y, n), n);
			d = gcd(abs(x - y), n);
		}
		if (d == n) {
			return -1;
		}
		return d;
	}
	vector<long long> factor(long long n) {
		if (n <= 1) {
			return {};
		}
		if (miller.check(n)) {
			return { n };
		}
		long long res = -1;
		while (res == -1) {
			res = check(n);
		}
		vector<long long> fa = factor(res);
		vector<long long> fb = factor(n / res);
		fa.insert(fa.end(), fb.begin(), fb.end());
		return fa;
	}
};

Rho rho;

void dfs(const map<ll, ll>& f, ll num, const map<ll, ll>::iterator &ite, vector<ll> &d) {
	if (ite == f.end()) {
		d.push_back(num);
		return;
	}
	rep(i, ite->second + 1) {
		dfs(f, num, next(ite), d);
		num *= ite->first;
	}
}

vector<ll> divisor(ll n) {
	map<ll, ll> mp;
	for (const auto& aa : rho.factor(n))++mp[aa];
	vector<ll>ret;
	dfs(mp, 1, mp.begin(), ret);
	return ret;
}
vector<long long> create(long long x) {
	vector<long long>v;
	for (long long i = 1; i*i*i <= x; ++i) {
		if (0 == (x % i))v.push_back(i);
	}
	return v;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q; cin >> q;
	while (q--) {
		long long s, t; cin >> s >> t;
		long long r = s * s * 16;
		if (0 != r % t) {
			cout << 0 << endl;
			continue;
		}
		r /= t;
		//vector<long long>vx = divisor(r);
		vector<long long>vx = create(r);
		sort(all(vx));
		//r = x*y*(t-x-y)
		vector<pair<long long, pair<long long, long long>>>ans;
		rep(i, vx.size()) {
			long long x = vx[i];
			long long rx = r / x;
			//rx = y(t-x-y)
			//y=((t-x)±sqrt((x-t)^2-4*rx))/2
			long long sq = cheker((x - t) *(x - t) - 4 * rx);
			if (-1 == sq)continue;
			if (0 != abs(t - x - sq) % 2)continue;
			rep(j, 2) {
				long long y = (t - x - sq) / 2;
				if (1 == j) (t - x + sq) / 2;
				if (y > 0) {
					long long z = t - x - y;
					if (z > 0) {
						if ((0 == (abs(x - y) % 2)) && (0 == (abs(x - z) % 2))) {
							vector<int>abc(3);
							abc[0] = (x + y) / 2;
							abc[1] = (x + z) / 2;
							abc[2] = (y + z) / 2;
							sort(all(abc));
							ans.push_back({ abc[0],{abc[1],abc[2]} });
							//cout << abc[0] << abc[1] << abc[2] << endl;
						}
					}
				}
			}
		}
		sort(all(ans));
		ans.erase(unique(all(ans)), ans.end());
		cout << ans.size() << endl;
		for (auto abc : ans) {
			cout << abc.first << " " << abc.second.first << " " << abc.second.second << endl;
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード