結果
| 問題 | No.3663 LCM Decomposition |
| コンテスト | |
| ユーザー |
 edon8618
|
| 提出日時 | 2026-08-30 15:58:20 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 166 ms / 1,000 ms |
| + 589µs | |
| コード長 | 7,023 bytes |
| 記録 | |
| コンパイル時間 | 5,680 ms |
| コンパイル使用メモリ | 425,620 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-08-30 15:58:29 |
| 合計ジャッジ時間 | 8,425 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 14 |
ソースコード
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define ll long long
#define ld long double
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
template<class T, class U>
inline bool chmax(T &a, const U &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class T, class U>
inline bool chmin(T &a, const U &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
// #define ll int
// #define ll int128_t
// #define ll int256_t
// #define ll cpp_int
constexpr ll inf = (1ll << 61);
// constexpr ll inf = (1 << 30);
// const double PI=3.1415926535897932384626433832795028841971;
uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123;
inline uint32_t xor_next() {
uint32_t t = xor_x ^ (xor_x << 11);
xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8));
}
inline int rnd(int max_val) { return xor_next() % max_val; }
struct Timer {
std::chrono::steady_clock::time_point start_time;
Timer() {
reset();
}
// 測定の起点リセット用
void reset() {
start_time = std::chrono::steady_clock::now();
}
// スタートからの経過時間をミリ秒(msec)で返す
long long get_ms() const {
auto now = std::chrono::steady_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time).count();
}
};
// ll rui(ll a,ll b){
// if(b==0)return 1;
// if(b%2==1) return a*rui(a*a,b/2);
// return rui(a*a,b/2);
// }
// vl fact;
// ll kai(ll n){
// fact.resize(n,1);
// rep(i,n-1)fact[i+1]=fact[i]*(i+1);
// }
// using mint = ld;
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly
// using mint = static_modint<469762049>; // ntt-friendly
// using mint = static_modint<167772161>; // ntt-friendly
// using mint = modint;//mint::set_mod(mod);
// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
// a%=mod;
// if(b==0)return 1;
// if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
// return modrui(a*a%mod,b/2,mod)%mod;
// }
// void incr(vl &v,ll n){// n進法
// ll k=v.size();
// v[k-1]++;
// ll now=k-1;
// while (v[now]>=n)
// {
// v[now]=0;
// if(now==0)break;
// v[now-1]++;
// now--;
// }
// return;
// }
vector<mint> fact,invf;
void init_modfact(ll sz){
fact.resize(sz);
invf.resize(sz);
fact[0]=1;
rep(i,sz-1){
fact[i+1]=fact[i]*(i+1);
}
invf[sz-1]=1/fact[sz-1];
for(ll i=sz-2; i>=0; i--){
invf[i]=invf[i+1]*(i+1);
}
}
mint choose(ll n,ll r){
if(n<r || r<0 || n<0)return 0;
return fact[n]*invf[r]*invf[n-r];
}
// vector<mint> modpow,invpow;
// void init_modpow(ll x,ll sz){
// mint inv=1/mint(x);
// modpow.assign(sz,1);
// invpow.assign(sz,1);
// rep(i,sz-1){
// modpow[i+1]=modpow[i]*x;
// invpow[i+1]=invpow[i]*inv;
// }
// }
// long long phi(long long n) {// O(sqrt(n))
// long long res = n;
// for (long long i = 2; i * i <= n; i++) {
// if (n % i == 0) {
// res -= res / i;
// while (n % i == 0) n /= i;
// }
// }
// if (n > 1) res -= res / n;
// return res;
// }
void solve(){
ll n,l,r;
cin >> n >> l >> r;
vl ds(0);
vl p(0);
for(ll d=1;d*d<=n;d++){
if(n%d==0){
p.push_back(d);
if(l<=d && d<=r)ds.push_back(d);
if(d*d!=n){
p.push_back(n/d);
if(l<=n/d && n/d<=r)ds.push_back(n/d);
}
}
}
sort(all(ds));
sort(all(p));
vl dec;
{
ll x=n;
for(auto d:p){
if(d==1)continue;
if(d>x)break;
ll s=1;
while(x%d==0){
x/=d;
s*=d;
}
if(s!=1)dec.push_back(s);
}
for(auto s:dec){
cerr << s << " ";
}cerr << endl;
}
vector<vl> v(1<<dec.size(),vl(0));
for(auto d:ds){
ll bit=0;
rep(i,dec.size()){
ll s=dec[i];
if(d%s==0)bit|=(1<<i);
}
if(v[bit].size()<3)v[bit].push_back(d);
}
ll sz=dec.size();
if(!v[(1<<sz)-1].empty()){
ll a=v[(1<<sz)-1][0];
ll b=-1,c=-1;
for(auto d:ds){
if(b==-1){
if(d!=a)b=d;
}
else if(c==-1){
if(d!=a && d!=b)c=d;
}
}
if(c==-1){
cout << -1 << endl;
return;
}
vl ans={a,b,c};
sort(all(ans));
rep(i,3){
cout << ans[i] << " \n"[i==2];
}return;
}
vl dp1(1<<sz,-1);
rep(i,1<<sz){
if(!v[i].empty())dp1[i]=v[i].front();
}
vector<array<ll,2>> dp2(1<<sz,{-1,-1});
rep(bit,1<<sz)rep(cit,1<<sz){
if(bit==cit)continue;
if(dp1[bit]!=-1 && !v[cit].empty())dp2[bit|cit]={dp1[bit],v[cit].front()};
}
vector<array<ll,3>> dp3(1<<sz,{-1,-1,-1});
rep(bit,1<<sz)rep(cit,1<<sz){
if((bit|cit)==bit)continue;
if(dp2[bit][0]!=-1 && !v[cit].empty())dp3[bit|cit]={dp2[bit][0],dp2[bit][1],v[cit].front()};
}
if(dp3[(1<<sz)-1][0]!=-1){
sort(all(dp3[(1<<sz)-1]));
rep(i,3){
cout << dp3[(1<<sz)-1][i] << " \n"[i==2];
}return;
}
if(dp2[(1<<sz)-1][0]!=-1){
ll a=dp2[(1<<sz)-1][0];
ll b=dp2[(1<<sz)-1][1];
ll c=-1;
for(auto d:ds){
if(b==-1){
if(d!=a)b=d;
}
else if(c==-1){
if(d!=a && d!=b)c=d;
}
}
if(c==-1){
cout << -1 << endl;
return;
}
vl ans={a,b,c};
sort(all(ans));
rep(i,3){
cout << ans[i] << " \n"[i==2];
}return;
}
cout << -1 << endl;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// ll mx=450;
// vc fl(mx+1,0);
// for(ll d=2;d<=mx;d++){
// if(fl[d])continue;
// ll x=d;
// ps.push_back(x);
// while(x<=mx){
// fl[x]=1;
// x+=d;
// }
// }
ll t = 1;
cin >> t;
while (t--){
solve();
}
}