結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー MM
提出日時 2026-08-30 15:30:40
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,863 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,648 ms
コンパイル使用メモリ 390,368 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-30 15:30:52
合計ジャッジ時間 11,336 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 1 RE * 7 TLE * 3 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
#define chmin(x,y) (x) = min((x),(y))
#define chmax(x,y) (x) = max((x),(y))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec vector
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back 
#define eb emplace_back

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
const ll mod = 998244353;
using mint = modint998244353;
const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};
// using Graph = vector<vector<pair<int,ll>>>;
using Graph = vector<vector<int>>;

vec<pair<ll,ll>> pf(ll X){
  if(X == 1) return {make_pair(1LL,1)};

  vec<pair<ll,ll>> res;
  for(ll i = 2; i * i <= X; i++)
    if(X % i == 0){
      int e = 0;
      while(X % i == 0){
        X /= i;
        e++;
      }
      res.eb(i,e);
    }

  if(X != 1) res.eb(X,1);
  return res;
}

vector<pair<ll,ll>> get_divisors(
  ll N,
  ll L,
  ll R,
  vector<pair<ll,ll>> PF
){
  int K = (int)PF.size();
  vec<pair<ll,ll>> res;
  bool have_N = 0;
  for(ll i = 1; i * i <= N; i++){
    if(N % i != 0) continue;

    if(i * i != N && L <= (N/i) && (N/i) <= R){
      int id = 0, x = N/i;
      rep(j,K){
        auto[p,e] = PF[j];
        int E = 0;
        while(x % p == 0){
          x /= p;
          E++;
        }
        if(E == e) id |= (1<<j);
      }
      // if(id > 0) 
      res.eb(N/i,id); 
      if(N/i == N) have_N = 1;     
    }

    if(L <= i && i <= R){
      int id = 0, x = i;
      rep(j,K){
        auto[p,e] = PF[j];
        int E = 0;
        while(x % p == 0){
          x /= p;
          E++;
        }
        if(E == e) id |= (1<<j);
      }
      // if(id > 0 || have_N) 
        res.eb(i,id);
    }
    
    if(have_N && res.size() >= 3) break;
  }
  return res;
}

int main(){
  // input
  int T;
  cin >> T;
  while(T--){
    ll N,L,R;
    cin >> N >> L >> R;
    auto PFN = pf(N);
    int K = PFN.size();
    // for(auto[p,e]:PFN)
    //   cerr << p << " " << e << endl;

    if(N == 1){
      cout << -1 << endl;
      continue;
    }
    auto cand = get_divisors(N,L,R,PFN);
    // cerr << "DEBUG: " << (int)cand.size() << endl;
    // for(auto [d,id] : cand)
    //   cerr << d << " " << id << endl;

    if(cand[0].first == N){
      if(cand.size() >= 3)
        cout << cand[0].first << " " << cand[1].first << " " << cand[2].first << endl;
      else
        cout << -1 << endl;
      continue;
    }

    bool found = 0;
    for(auto[a,x] : cand){
      for(auto[b,y] : cand){
        if(b <= a) continue;
        for(auto[c,z] : cand){
          if(c <= b) continue;
          if(((x|y)|z) == (1<<K)-1){
            cout << a << " " << b << " " << c << endl;
            found = 1;
            break;
          }
        }
        if(found) break;
      }
      if(found) break;
    }
    if(!found) cout << -1 << endl;
  }
}
0