#1181764 (C++17) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: tnakao0123
• 提出日時: 2026-08-31 13:10:21
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,792 bytes
• コンパイル時間: 822 ms
• コンパイル使用メモリ: 92,024 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-31 13:10:41
• 合計ジャッジ時間: 3,111 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 11 WA * 3

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3663.cc:  No.3663 LCM Decomposition - yukicoder
 */

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_P = 32000;
const int MAX_K = 9;
const int KBITS = 1 << MAX_K;

/* typedef */

using vb = vector<bool>;
using vi = vector<int>;
using si = set<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

/* global variables */

vb primes;
vi pnums;
int eps[MAX_K], cs[MAX_K];
vi bds[KBITS];
si bqs[KBITS];

/* subroutines */

int gen_primes(int maxp) {
  primes.assign(maxp + 1, true);
  primes[0] = primes[1] = false;
  pnums.clear();

  int p;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums.push_back(p);
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums.push_back(p);
  return (int)pnums.size();
}

vpii prime_decomp(int n) {
  vpii pds;

  for (auto pi: pnums) {
    if (pi * pi > n) {
      if (n > 1) pds.push_back(pii(n, 1));
      break;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      pds.push_back(pii(pi, fi));
    }
  }
  return pds;
}

int powi(int a, int b) {
  int p = 1;
  while (b > 0) {
    if (b & 1) p *= a;
    a *= a;
    b >>= 1;
  }
  return p;
}

int powi(pii &pd) { return powi(pd.first, pd.second); }

int pds2i(vpii &pds) {
  int n = 1;
  for (auto [p, d]: pds) n *= powi(p, d);
  return n;
}

vi merge(si &bq0, si &bq1, si &bq2) {
  for (auto q0: bq0)
    for (auto q1: bq1)
      if (q0 != q1)
	for (auto q2: bq2)
	  if (q0 != q2 && q1 != q2) {
	    vi v{q0, q1, q2};
	    sort(v.begin(), v.end());
	    return v;
	  }
  return {};
}

/* main */

int main() {
  gen_primes(MAX_P);

  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n, l, r;
    scanf("%d%d%d", &n, &l, &r);

    auto pds = prime_decomp(n);
    int k = (int)pds.size();

    for (int i = 0; i < k; i++) eps[i] = powi(pds[i]);
    //for (int i = 0; i < k; i++) printf(" %d", eps[i]); putchar('\n');

    vi ds;
    for (int p = 1; p * p <= n; p++)
      if (n % p == 0) {
	if (l <= p && p <= r) ds.push_back(p);
	int q = n / p;
	if (q != p && l <= q && q <= r) ds.push_back(q);
      }
    if (ds.size() < 3) { puts("-1"); continue; }
    sort(ds.begin(), ds.end());
    //for (auto d: ds) printf(" %d", d); putchar('\n');

    int kbits = 1 << k;
    for (int bits = 0; bits < kbits; bits++) bds[bits].clear();
    for (auto d: ds) {
      int bits = 0;
      for (int i = 0, bi = 1; i < k; i++, bi <<= 1)
	if (d % eps[i] == 0) bits |= bi;
      if (bds[bits].size() < 3) bds[bits].push_back(d);
    }
    //for (int bits = 0; bits < kbits; bits++) {
    //  printf(" %d:", bits);
    //  for (auto d: bds[bits]) printf(" %d", d); putchar('\n');
    //}

    for (int bits = 0; bits < kbits; bits++) bqs[bits].clear();
    for (int i = 0; i < 3; i++) bqs[0].insert(ds[i]);
    for (int bits = 1; bits < kbits; bits++) {
      for (int bits0 = bits; bits0 > 0; bits0 = (bits0 - 1) & bits)
	for (auto d: bds[bits0]) {
	  if (bqs[bits0].size() >= 3) break;
	  bqs[bits0].insert(d);
	}
    }
    //for (int bits = 0; bits < kbits; bits++) {
    //  printf(" %d:", bits);
    //  for (auto q: bqs[bits]) printf(" %d", q); putchar('\n');
    //}

    fill(cs, cs + k, 0);
    bool found = false;
    for (;;) {
      int bits[3] = {};
      for (int i = 0; i < k; i++)
	bits[cs[i]] |= (1 << i);

      auto v = merge(bqs[bits[0]], bqs[bits[1]], bqs[bits[2]]);
      if (! v.empty()) {
	printf("%d %d %d\n", v[0], v[1], v[2]);
	found = true;
	break;
      }
      
      int l = 0;
      while (l < k) {
	if (++cs[l] > 2) cs[l++] = 0;
	else break;
      }
      if (l >= k) break;
    }

    if (! found) puts("-1");
  }
  
  return 0;
}