ARC108に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
- A問題
- B問題
結果
- コンテスト結果
- パフォーマンス、レーティング変動
反省点

解いた/挑んだ問題

A問題

問題の概要

整数 $S,P$ が与えらます。
$N + M = S, N × M = P$ を満たすような正の整数の組 $(N,M)$ はあるか

制約

入力はすべて整数
$1 \leq S,P \leq 10^{12}$

どのように考えたか

Pの約数を配列Aに格納し、 $S - A_i$ となるような値がAに存在するかどうかを二部探索で判定する

結果

二回目でAC
・提出ししたコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

//約数列挙
vector<ll> enum_divisors(ll N) {
	vector<ll> res;
	for (ll i = 1; i * i <= N; ++i) {
		if (N % i == 0) {
			res.push_back(i);
			// 重複しないならば i の相方である N/i も push
			if (N / i != i) res.push_back(N / i);
		}
	}
	// 小さい順に並び替える
	sort(all(res));
	return res;
}

int main() {
	ll s,p,key;
	bool ans = false;
	cin >> s >> p;
	auto st = enum_divisors(p);
	for(int i = 0;i < st.size();i++){
		key = s - st[i];
		if(key < 0)break;
		if(binary_search(all(st),key)){
			ans = true;
			break;
		}
	}
	//Yes/Noを返す
	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}