結果
| 問題 | No.3485 Find 495-like Number |
| コンテスト | |
| ユーザー |
 nouka28
|
| 提出日時 | 2026-03-27 22:12:25 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 313 ms / 5,000 ms |
| コード長 | 11,683 bytes |
| 記録 | |
| コンパイル時間 | 7,115 ms |
| コンパイル使用メモリ | 391,188 KB |
| 実行使用メモリ | 81,664 KB |
| 最終ジャッジ日時 | 2026-03-27 22:13:12 |
| 合計ジャッジ時間 | 19,341 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;
template<class T> bool chmax(T &a,T b){return (a<b)?a=b,1:0;}
template<class T> bool chmin(T &a,T b){return (a>b)?a=b,1:0;}
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
//math
namespace nouka28{
random_device rnd;
mt19937 mt(rnd());
const long long MT_MAX=(1LL<<62)-1;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
// [a,b]の乱数を生成
return a+rd(mt)%(b-a+1);
}
template<class T=long long>
vector<T> Quotients(T n){
vector<T> retl,retr;
for(int i=1;i*i<=n;i++){
retl.push_back(i);
if(i<n/i)retr.push_back(n/i);
}
reverse(retr.begin(),retr.end());
retl.insert(retl.end(),retr.begin(),retr.end());
return retl;
}
template<class T=long long>T ceil_sqrt(T n){
T l=-1,r=n;
while(r-l>1){
T m=(l+r)>>1;
if(m*m>=n)r=m;
else l=m;
}
return r;
}
//ceil(a/b)
template<class T=long long>T ceil(T a,T b){
if(a>=0){
return (a+b-1)/b;
}else{
return (a)/b;
}
};
//floor(a/b)
template<class T=long long>T floor(T a,T b){
if(a>=0){
return a/b;
}else{
return -(-a+b-1)/b;
}
};
//x^y mod m
template<class T=long long>T modpow(T x,T y,T m){
T res=1%m;x%=m;
while(y){
if(y%2)res=(res*x)%m;
x=(x*x)%m;
y>>=1;
}
return res;
}
//a^0+a^1+..+a^(n-1) (mod m)
template<class T>
T geometric_progression(T a,T n,T m){
if(n==0)return 0;
if(n%2==1){
return (geometric_progression(a,n-1,m)*a+1)%m;
}else{
return (geometric_progression(a*a%m,n/2,m)*(1+a))%m;
}
};
//素数判定(高速)
bool is_prime(long long n){
if(n<=1)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
long long s=0,d=n-1;
while(d%2==0)d/=2,s++;
if(n<4759123141LL){
for(long long e:{2,7,61}){
if(n<=e)break;
long long t,x=modpow<__int128_t>(e,d,n);
if(x!=1){
for(t=0;t<s;t++){
if(x==n-1)break;
x=__int128_t(x)*x%n;
}
if(t==s)return 0;
}
}
return 1;
}else{
for(long long e:{2,325,9375,28178,450775,9780504,1795265022}){
if(n<=e)break;
long long t,x=modpow<__int128_t>(e,d,n);
if(x!=1){
for(t=0;t<s;t++){
if(x==n-1)break;
x=__int128_t(x)*x%n;
}
if(t==s)return 0;
}
}
return 1;
}
}
//Xor Shift
unsigned xor_shift_rng(){
static unsigned tx=123456789,ty=362436069,tz=521288629,tw=88675123;
unsigned tt=(tx^(tx<<11));
tx=ty,ty=tz,tz=tw;
return (tw=(tw^(tw>>19))^(tt^(tt>>8)));
}
//ロー法 Nを割り切る素数を見つける
long long pollard(long long n){
if(n%2==0)return 2;
if(is_prime(n))return n;
long long step=0;
while(true){
long long r=(long long)xor_shift_rng();
auto f=[&](long long x)->long long {return ((__int128_t(x)*x)%n+r)%n;};
long long x=++step,y=f(x);
while(true){
long long p=gcd(abs(y-x),n);
if(p==0||p==n)break;
if(p!=1)return p;
x=f(x);
y=f(f(y));
}
}
}
//internal fast factrize vector
void _internal_factrize_vector(long long n,vector<long long>&v){
if(n==1)return;
long long p=pollard(n);
if(p==n){v.push_back(p);return;}
_internal_factrize_vector(p,v);
_internal_factrize_vector(n/p,v);
}
//fast factrize vector
vector<long long> factrize_vector(long long n){
vector<long long> res;
_internal_factrize_vector(n,res);
sort(res.begin(),res.end());
return res;
}
//internal fast factrize map
void _internal_factrize_map(long long n,map<long long,long long>&v){
if(n==1)return;
long long p=pollard(n);
if(p==n){v[p]++;return;}
_internal_factrize_map(p,v);
_internal_factrize_map(n/p,v);
}
//fast factrize map
map<long long,long long> factrize_map(long long n){
map<long long,long long> res;
_internal_factrize_map(n,res);
return res;
}
//fast factor
vector<long long> factor(long long n){
map<long long,long long> fm;_internal_factrize_map(n,fm);
vector<long long> res={1};
for(auto[i,j]:fm){
vector<long long> tmp;
int p=1;
for(long long k=0;k<=j;k++){
for(auto e:res){
tmp.push_back(e*p);
}
p*=i;
}
swap(res,tmp);
}
return res;
}
//euler phi function
long long euler_phi(long long n){
vector<long long> ps=factrize_vector(n);
ps.erase(unique(ps.begin(),ps.end()),ps.end());
for(long long p:ps){
n/=p;n*=(p-1);
}
return n;
}
//ax+by=gcd(a,b)
template<class T=long long>
tuple<T,T,T> extgcd(T a,T b){
T x1=1,y1=0,d1=a,x2=0,y2=1,d2=b;
while(d2!=0){
T q=d1/d2,u=d1-d2*q,v=x1-x2*q,w=y1-y2*q;
d1=d2;d2=u;x1=x2;x2=v;y1=y2;y2=w;
}
if(d1<0){
d1=-d1;x1=-x1;y1=-y1;
}
return {d1,x1,y1};
}
//x inverse (mod m)
long long modinv(long long a,long long m){
long long b=m,u=1,v=0;
while(b){
long long t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
u%=m;
if(u<0)u+=m;
return u;
}
//find primitive root
long long primitive_root(long long p){
vector<long long> f=factrize_vector(p-1);
f.erase(unique(f.begin(),f.end()),f.end());
while(1){
long long x=randint(1,p-1);
bool flg=1;
for(auto e:f)if(modpow<__int128_t>(x,(p-1)/e,p)==1){flg=0;break;}
if(flg)return x;
}
}
//x^k=y (mod m) gcd(x,m)=1 k>=0
long long discrete_logarithm_coprime_mod(long long x,long long y,long long m){
x%=m;y%=m;
if(y==1||m==1){
return 0;
}
if(x==0){
if(y==0)return 1;
else return -1;
}
long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
unordered_map<long long,long long> mp;
long long pow_x=1;
for(long long i=0;i<M;i++){
if(!mp.count(pow_x))mp[pow_x]=i;
pow_x=pow_x*x%m;
}
long long ya=y;
for(long long i=0;i<M;i++){
if(mp.count(ya))return M*i+mp[ya];
ya=ya*a%m;
}
return -1;
}
//x^k=y (mod m) gcd(x,m)=1 k>=1
long long discrete_Nlogarithm_coprime_mod(long long x,long long y,long long m){
if(m==1){
if(x==1)return 1;
else return -1;
}
if(x==0){
if(y==0)return 1;
else return -1;
}
long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
unordered_map<long long,long long> mp;
long long pow_x=1;
for(long long i=0;i<=M;i++){
if(!mp.count(pow_x))mp[pow_x]=i;
pow_x=pow_x*x%m;
}
long long ya=y;
for(long long i=0;i<M;i++){
if(ya==1&&i>0)return i*M;
else if(mp.count(ya))return M*i+mp[ya];
ya=ya*a%m;
}
return -1;
}
//x^k=y (mod m) k>=0
long long discrete_logarithm_arbitrary_mod(long long x,long long y,long long m){
if(m==1){
return 0;
}
x%=m;y%=m;
long long d,pow_x=1;
for(d=0;;d++){
if(!(m>>d))break;
if(pow_x==y){
return d;
}
pow_x=pow_x*x%m;
}
long long g=gcd(pow_x,m);
if(y%g!=0){
return -1;
}
m/=g;
long long z=y*modinv(pow_x,m),t=discrete_logarithm_coprime_mod(x,z,m);
if(t==-1)return -1;
else return d+t;
}
//x^k=y (mod m) k>=1
long long discrete_Nlogarithm_arbitrary_mod(long long x,long long y,long long m){
if(m==1){
if(x==1)return 1;
else return -1;
}
x%=m;y%=m;
long long d,pow_x=1;
for(d=0;;d++){
if(!(m>>d))break;
if(pow_x==y&&d){
return d;
}
pow_x=pow_x*x%m;
}
long long g=gcd(pow_x,m);
if(y%g!=0){
return -1;
}
m/=g;
long long z=y*modinv(pow_x,m),t;
if(d)t=discrete_logarithm_coprime_mod(x,z,m);
else t=discrete_Nlogarithm_coprime_mod(x,y,m);
if(t==-1)return -1;
else return d+t;
}
}
struct FastFactrize{
vector<int> SPF;
FastFactrize(int N):SPF(N+1,1){
for(int i=2;i<=N;i++){
if(SPF[i]!=1)continue;
for(int j=i;j<=N;j+=i){
if(SPF[j]==1)SPF[j]=i;
}
}
};
vector<int> factrize_vector(int n){
vector<int> ret;
while(SPF[n]!=1){
ret.push_back(SPF[n]);
n/=SPF[n];
}
return ret;
}
vector<int> factrize_set(int n){
vector<int> ret=factrize_vector(n);
ret.erase(unique(ret.begin(),ret.end()),ret.end());
return ret;
}
map<int,int> factrize_map(int n){
map<int,int> ret;
while(SPF[n]!=1){
ret[SPF[n]]++;
n/=SPF[n];
}
return ret;
}
vector<int> factor(int n){
vector<int> ret={1};
for(auto[i,j]:factrize_map(n)){
vector<int> nret;
for(int e:ret){
int x=1;
for(int e2=0;e2<=j;e2++){
nret.push_back(e*x);
x*=i;
}
}
swap(ret,nret);
}
return ret;
}
};
using namespace nouka28;
signed main(){
int L,R;cin>>L>>R;
FastFactrize ff(1e7);
auto get=[&](int X)->pair<int,int> {
if(X<=1e7){
if(ff.SPF[X]==X){
return {-1,-1};
}else{
int y=ff.SPF[X/ff.SPF[X]];
if(ff.SPF[y]==y){
return {min(ff.SPF[X],y),max(ff.SPF[X],y)};
}else{
return {-1,-1};
}
}
}else{
int u=pollard(X);
if(is_prime(X/u)){
return {min(u,X/u),max(u,X/u)};
}else{
return {-1,-1};
}
}
};
for(int a=3;a*a*(a+2)*(a+4)<=R;a+=2){
int L2=(L+a*a-1)/(a*a);
int R2=R/(a*a);
for(int i=L2;i<=R2;i++){
auto[x,y]=get(i);
if(x==-1)continue;
if(a<x&&x<y&&(x%2)&&(y%2)){
cout<<a*a*x*y<<"\n";
// cout<<a<<" "<<a<<" "<<x<<" "<<y<<"\n";
return 0;
}
}
}
cout<<-1<<"\n";
}