結果
| 問題 | No.3663 LCM Decomposition |
| コンテスト | |
| ユーザー |
 detteiuu
|
| 提出日時 | 2026-08-30 15:27:46 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 125 ms / 1,000 ms |
| + 556µs | |
| コード長 | 5,843 bytes |
| 記録 | |
| コンパイル時間 | 8,880 ms |
| コンパイル使用メモリ | 432,656 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-08-30 15:27:59 |
| 合計ジャッジ時間 | 11,361 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 14 |
コンパイルメッセージ
main.cpp: In function 'pll func(ll, vl&, vl&, vl&)':
main.cpp:93:19: warning: 'idx' may be used uninitialized [-Wmaybe-uninitialized]
93 | if ((B[idx]|B[i]) == base) {
| ^
main.cpp:82:8: note: 'idx' was declared here
82 | ll idx;
| ^~~
main.cpp:98:17: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized]
98 | return {a, b};
| ^
main.cpp:81:11: note: 'b' was declared here
81 | ll a, b;
| ^
main.cpp:98:17: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]
98 | return {a, b};
| ^
main.cpp:81:8: note: 'a' was declared here
81 | ll a, b;
| ^
ソースコード
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define repr2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define YesNo(cond) cout << ((cond) ? "Yes\n" : "No\n")
#define YESNO(cond) cout << ((cond) ? "YES\n" : "NO\n")
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
template <typename T> void print(const T& value) { cout << value << "\n"; }
template <typename T> void print(const vector<T>& vec) { for (auto& v : vec) cout << v << " "; cout << "\n"; }
template <typename T> void input(vector<T>& vec) { for (auto& v : vec) cin >> v; };
template <typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;
vector<long long> divisor(long long n, ll L, ll R) {
vector<long long> ans;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (L <= i && i <= R) ans.push_back(i);
if (i * i != n) {
if (L <= n/i && n/i <= R) ans.push_back(n / i);
}
}
}
sort(all(ans));
return ans;
}
vector<pair<long long, long long>> factorization(long long n) {
vector<pair<long long, long long>> res;
long long temp = n;
// 上限は ceil(sqrt(n))
for (long long i = 2; i * i <= temp; i++) {
if (temp % i == 0) {
long long cnt = 0;
while (temp % i == 0) {
temp /= i;
cnt++;
}
res.push_back({i, cnt});
}
}
if (temp != 1) {
res.push_back({temp, 1});
}
if (res.empty()) {
res.push_back({n, 1});
}
return res;
}
pll func(ll base, vl& dp2, vl& div, vl& B) {
ll a, b;
ll idx;
rep (i, sz(div)) {
ll d = div[i];
if (dp2[base^B[i]] != 0) {
a = d;
idx = i;
break;
}
}
rep (i, sz(div)) {
ll d = div[i];
if ((B[idx]|B[i]) == base) {
b = d;
break;
}
}
return {a, b};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
int T; cin >> T;
while (T--) {
ll N, L, R;
cin >> N >> L >> R;
if (N == 1) {
print(-1);
continue;
}
auto div = divisor(N, L, R);
if (sz(div) < 3) {
print(-1);
continue;
}
if (R == N) {
print(format("{} {} {}", div[sz(div)-3], div[sz(div)-2], div[sz(div)-1]));
continue;
}
auto fact = factorization(N);
ll size = sz(fact);
vl dp(1<<size, 0);
vl B;
for (auto d : div) {
ll bit = 0;
rep (i, size) {
auto n = d;
rep (_, fact[i].second-1) {
if (n%fact[i].first == 0) {
n /= fact[i].first;
}
}
if (n%fact[i].first == 0) {
bit |= 1<<i;
}
}
dp[bit] = 1;
B.push_back(bit);
}
vl dp2 = dp;
rep (i, size) {
rep (bit, 1<<size) {
if (((1<<i) & bit) == 0) {
dp[bit|(1<<i)] += dp[bit];
}
}
}
rep (bit, 1<<size) {
dp[bit] *= dp[bit];
}
rep (i, size) {
repr (bit, 1<<size) {
if (((1<<i) & bit) != 0) {
dp[bit] -= dp[bit^(1<<i)];
}
}
}
rep (i, size) {
repr (bit, 1<<size) {
if (((1<<i) & bit) != 0) {
dp2[bit^(1<<i)] += dp2[bit];
}
}
}
// 2つで作れる場合
if (dp[sz(dp)-1] != 0) {
ll base = (1<<size)-1;
ll c;
c = -1;
auto [a, b] = func(base, dp2, div, B);
rep (i, sz(div)) {
ll d = div[i];
if (a != d && b != d) {
c = d;
break;
}
}
vl S = {a, b, c};
sort(all(S));
print(S);
continue;
}
// 3つで作れる場合
vl dp3 = dp;
rep (i, size) {
repr (bit, 1<<size) {
if (((1<<i) & bit) != 0) {
dp3[bit^(1<<i)] += dp[bit];
}
}
}
ll a;
a = -1;
ll idx = -1;
ll base = (1<<size)-1;
rep (i, sz(div)) {
ll d = div[i];
if (dp3[base^B[i]] != 0) {
a = d;
idx = i;
break;
}
}
if (a == -1) {
print(-1);
continue;
}
rep (bit, 1<<size) {
if ((B[idx]|bit) == base && dp[bit] != 0) {
base = bit;
break;
}
}
auto [b, c] = func(base, dp2, div, B);
vl S = {a, b, c};
sort(all(S));
print(S);
}
}