結果

問題 No.3127 Multiple of Twin Prime
コンテスト
ユーザー jiyujin816
提出日時 2025-04-25 22:01:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 183 ms / 2,500 ms
コード長 3,494 bytes
コンパイル時間 3,869 ms
コンパイル使用メモリ 286,248 KB
実行使用メモリ 90,852 KB
最終ジャッジ日時 2025-04-25 22:02:18
合計ジャッジ時間 7,737 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//以下cout時の色設定
#define COUTRESET "\033[0m" // 色をリセット
#define COUTRED "\033[31m" // 赤色
#define COUTGREEN "\033[32m" // 緑色
#define COUTYELLOW "\033[33m" // 黄色
#define COUTBLUE "\033[34m" // 青色
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using P=pair<ll,ll>;
const ll INF=1e17; 
const vector<ll> dx={0,0,1,-1,1,1,-1,-1};
const vector<ll> dy={1,-1,0,0,1,-1,-1,1};
#define rep(i,N) for(int i=0;i<N;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
template <typename T1,typename T2>
ostream& operator<<(ostream &os,pair<T1,T2> &pai){
    return os<<"("<<pai.first<<","<<pai.second<<") ";
}
template<typename T>
ostream& operator<<(ostream &os,vector<T> vec){
    for(auto val:vec){
        os<<val<<" ";
    }
    return os<<"\n";
}
template<typename T>
istream& operator>>(istream &is,vector<T> &vec){
    for(int i=0;i<(int)vec.size();i++){
        is>>vec[i];
    }
    return is;
}
template<typename T,typename T2>
istream& operator>>(istream &is,pair<T,T2> &pai){
    is>>pai.first>>pai.second;
    return is;
}
template <typename T> void print(const T &vec){
    int i=0;
    for(auto val:vec){
        cout<<i<<":"<<val<<",";
        i++;
    }
    cout<<'\n';
}
template<typename T> void print2(const vector<vector<T>> &vec){
    int i=0;
    for(auto v:vec){
        cout<<i<<": ";
        for(auto a:v){
            cout<<a<<" ";
        }
        i++;
        cout<<'\n';
    }
}
template<class T> void chmin(T &a,T b){
    if(a>b){
        a=b;
    }
    return;
}
template<class T> void chmax(T &a,T b){
    if(a<b){
        a=b;
    }
    return;
}
struct Eratosthenes{
    ll r;
    vector<ll> min_divi;
    vector<bool> is_p;
    Eratosthenes(ll N){
        r=N;
        min_divi.resize(r+1,-1);
        is_p.resize(r+1,true);
        min_divi[0]=0;
        min_divi[1]=1;
        is_p[0]=false;
        is_p[1]=false;
        for(ll i=2;i*i<=r;i++){
            if(is_p[i]){
                for(ll j=2;i*j<=r;j++){
                    if(is_p[i*j]){
                        is_p[i*j]=false;
                        min_divi[i*j]=min(i,j);
                    }
                }
            }
        }

    }
    bool is_prime(ll n){
        assert(0<=n && n<=r);
        return is_p[n];
    }
    vector<ll> prime_fact(ll n){
        vector<ll> ret;
        while(n!=1){
            if(is_p[n]){
                ret.push_back(n);
                n/=n;
                break;
            }
            ret.push_back(min_divi[n]);
            n/=min_divi[n];
        }
        return ret;
    }
    
};
int main(){
    cin.tie(0)->sync_with_stdio(0);    
    int T;
    cin>>T;
    Eratosthenes et(10000005);
    vector<ll> prime;
    rep(i,10000004){
        if(et.is_prime(i+1)){
            prime.push_back(i+1);
        }
    }
    vector<ll> futago;
    rep(i,(int)prime.size()-1){
        if(prime[i]+2==prime[i+1]){
            futago.push_back(prime[i]);
        }
    }
    rep(i,T){
        ll N;
        cin>>N;
        if(N<15){
            cout<<-1<<"\n";
            continue;
        }
        ll sqN=1e8;
        ll ok=0;
        ll ng=1e8;
        while(abs(ok-ng)>1){
            ll mid=(ok+ng)/2;
            if(mid*mid+2*mid<=N){
                ok=mid;
            }else{
                ng=mid;
            }
        }
        sqN=ok;
        ll p=*(--upper_bound(all(futago),sqN));
        cout<<p*(p+2)<<"\n";
    }  
}
0