#1150669 (C++23) No.3461 Min GCD

提出ソース

結果

問題	No.3461 Min GCD
コンテスト
ユーザー	Tamiji153
提出日時	2026-02-28 16:19:40
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	WA
実行時間	-
コード長	10,958 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	6,236 ms
コンパイル使用メモリ	375,556 KB
実行使用メモリ	111,680 KB
最終ジャッジ日時	2026-02-28 16:19:59
合計ジャッジ時間	12,546 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

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

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'll3 tree_diam(const std::vector<std::vector<long long int> >&)':
main.cpp:245:21: warning: 'gl' may be used uninitialized [-Wmaybe-uninitialized]
  245 |     return {mx,st,gl};
      |                     ^
main.cpp:240:14: note: 'gl' was declared here
  240 |     mx=-1;ll gl;
      |              ^~
main.cpp:239:13: warning: 'st' may be used uninitialized [-Wmaybe-uninitialized]
  239 |     bfs_dist(G,M2,st);
      |     ~~~~~~~~^~~~~~~~~
main.cpp:233:14: note: 'st' was declared here
  233 |     ll mx=-1,st;
      |              ^~

ソースコード

raw source code

#ifdef __LOCAL
#define _GLIBCXX_DEBUG
#elifdef __GNUC__
#pragma GCC optimize("O3")
#endif
#include<bits/stdc++.h>
using namespace std;
#ifdef ORDSET
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using ld=long double;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define repr(i,n) for(ll i=(n)-1;i>=0;--i)
#define repa(i,a,b) for(ll i=(a);i<(b);++i)
#define repra(i,a,b) for(ll i=(b)-1;i>=(a);--i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
struct ll2{
    ll a,b;
    friend auto operator<=>(const ll2&,const ll2&)=default;
};
struct ll3{
    ll a,b,c;
    friend auto operator<=>(const ll3&,const ll3&)=default;
};
struct ll4{
    ll a,b,c,d;
    friend auto operator<=>(const ll4&,const ll4&)=default;
};
struct ll5{
    ll a,b,c,d,e;
    friend auto operator<=>(const ll5&,const ll5&)=default;
};
struct ll6{
    ll a,b,c,d,e,f;
    friend auto operator<=>(const ll6&,const ll6&)=default;
};
constexpr ll MOD=998244353LL;
constexpr ll MOD2=1000000007LL;
constexpr ll IMOD=11451445450721LL;
constexpr ll B10=1024LL;
constexpr ll B20=1048576LL;
constexpr ll B30=1073741824LL;
constexpr ll B40=1099511627776LL;
constexpr ll B50=1125899906842624LL;
constexpr ll B60=1152921504606846976LL;
constexpr ll INF=B60;
constexpr ll E3=1000LL;
constexpr ll E6=1000000LL;
constexpr ll E9=1000000000LL;
constexpr ll E10=10000000000LL;
constexpr ll E12=1000000000000LL;
constexpr ll E15=1000000000000000LL;
constexpr ll E18=1000000000000000000LL;
constexpr ll2 D2[]={{0,1},{1,0}};
constexpr ll2 D4[]={{-1,0},{0,-1},{0,1},{1,0}};
constexpr ll2 D8[]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
constexpr char ALPH[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr char alph[]="abcdefghijklmnopqrstuvwxyz";
ostream&operator<<(ostream&os,const ll2&o) {
    os<<o.a<<' '<<o.b;
    return os;
}
ostream&operator<<(ostream&os,const ll3&o) {
    os<<o.a<<' '<<o.b<<' '<<o.c;
    return os;
}
ostream&operator<<(ostream&os,const ll4&o) {
    os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d;
    return os;
}
ostream&operator<<(ostream&os,const ll5&o) {
    os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e;
    return os;
}
ostream&operator<<(ostream&os,const ll6&o) {
    os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e<<' '<<o.f;
    return os;
}
// Print Vector
template<typename T>
ostream&operator<<(ostream&os,const vector<T>&V) {
    for(auto a:V)os<<a<<' ';
    return os;
}
// Print Set
template<typename T>
ostream&operator<<(ostream&os,const set<T>&V) {
    for(auto a:V)os<<a<<' ';
    return os;
}
// Print MultiSet
template<typename T>
ostream&operator<<(ostream&os,const multiset<T>&V) {
    for(auto a:V)os<<a<<' ';
    return os;
}
// Mod Power
ll pow_mod(ll x,ll y,ll mod=MOD){
    if(y==0)return 1%mod;
    ll t=pow_mod(x,y>>1,mod);
    if(y&1)return t*t%mod*x%mod;
    return t*t%mod;
}
// Mod Inversion (Only Prime)
ll inv_mod(ll x,ll mod=MOD){
    return pow_mod(x,mod-2,mod);
}
// Factorial
pair<vector<ll>,vector<ll>> fact(ll n,ll mod=MOD,bool inv=true){
    vector<ll> ans(n+1,1),ians(n+1);
    rep(i,n)ans[i+1]=ans[i]*(i+1)%mod;
    ians[n]=inv_mod(ans[n],mod);
    repr(i,n)ians[i]=ians[i+1]*(i+1)%mod;
    return {ans,ians};
}
// Combination
ll comb(const vector<ll>&fct,const vector<ll>&ifct,ll n,ll r,ll mod=MOD){
    if(r<0||n<r||n<0)return 0;
    return fct[n]*ifct[r]%mod*ifct[n-r]%mod;
}
// Divisors
vector<ll> divisors(ll n){
    vector<ll> ans;
    repa(i,1,static_cast<ll>(sqrt(static_cast<double>(n)))+1){
        if(n%i==0){
            ans.push_back(i);
            if(i!=n/i)ans.push_back(n/i);
        }
    }
    return ans;
}
// BFS
void bfs_dist(const vector<vector<ll>>&G,vector<ll>&M,ll st){
    queue<ll> Q;
    Q.push(st);
    M[st]=0;
    while(!Q.empty()){
        ll p=Q.front();Q.pop();
        for(ll q:G[p]){
            if(M[p]+1<M[q]){
                M[q]=M[p]+1;
                Q.push(q);
            }
        }
    }
}
// BFS with Parents
void bfs_dist_par(const vector<vector<ll>>&G,vector<ll>&M,vector<ll>&P,ll st){
    queue<ll> Q;
    Q.push(st);
    M[st]=0;
    while(!Q.empty()){
        ll p=Q.front();Q.pop();
        for(ll q:G[p]){
            if(M[p]+1<M[q]){
                M[q]=M[p]+1;
                P[q]=p;
                Q.push(q);
            }
        }
    }
}
// 0-1BFS
void bfs01_dist(const vector<vector<ll2>>&G,vector<ll>&M,ll st){
    deque<ll> Q;
    Q.push_back(st);
    M[st]=0;
    while(!Q.empty()){
        ll p=Q.front();Q.pop_front();
        for(auto[d,q]:G[p]){
            if(M[p]+d<M[q]){
                M[q]=M[p]+d;
                if(d==1)Q.push_back(q);
                else Q.push_front(q);
            }
        }
    }
}
// Bellman-Ford
vector<ll> bellman_ford(ll n,const vector<ll3>&E,ll st){
    vector<ll> dis(n,INF);
    dis[st]=0;
    rep(i,n)for(auto[w,u,v]:E)if(dis[v]>dis[u]+w)dis[v]=dis[u]+w;
    for(auto[w,u,v]:E)if(dis[v]>dis[u]+w){
        rep(i,n)dis[i]=-INF;
        return dis;
    }
    return dis;
}
// Dijkstra
vector<ll> dijkstra(const vector<vector<ll2>>&G,ll st){
    ll n=G.size();
    priority_queue<ll2,vector<ll2>,greater<>> Q;
    Q.emplace(0,st);
    vector<ll> dis(n,INF);
    dis[st]=0;
    while(!Q.empty()){
        auto[d,p]=Q.top();Q.pop();
        if(d>dis[p])continue;
        for(auto[e,q]:G[p]){
            if(d+e<dis[q]){
                dis[q]=d+e;
                Q.emplace(d+e,q);
            }
        }
    }
    return dis;
}
// Warshall-Floyd
vector<vector<ll>> warshall_floyd(const vector<vector<ll>>&G){
    ll n=G.size();
    vector dis(n,vector<ll>(n));
    rep(i,n){
        rep(j,n)dis[i][j]=G[i][j];
        dis[i][i]=0;
    }
    rep(k,n)rep(i,n)rep(j,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    return dis;
}
// Tree Diamiter
ll3 tree_diam(const vector<vector<ll>>&G){
    ll n=G.size();
    vector<ll> M1(n,INF);
    bfs_dist(G,M1,0);
    ll mx=-1,st;
    rep(i,n)if(M1[i]>mx){
        mx=M1[i];
        st=i;
    }
    vector<ll> M2(n,INF);
    bfs_dist(G,M2,st);
    mx=-1;ll gl;
    rep(i,n)if(M2[i]>mx){
        mx=M2[i];
        gl=i;
    }
    return {mx,st,gl};
}
// Union-Find
struct union_find{
    vector<ll> par;
    explicit union_find(ll n):par(n,-1){}
    ll find(ll u){
        vector<ll> A;
        while(par[u]>=0){
            A.push_back(u);
            u=par[u];
        }
        rep(i,A.size())par[A[i]]=u;
        return u;
    }
    bool same(ll u,ll v){return find(u)==find(v);}
    void merge(ll u,ll v){
        u=find(u);
        v=find(v);
        if(u==v)return;
        if(par[u]>par[v])swap(u,v);
        par[u]+=par[v];
        par[v]=u;
    }
};
// Weighted Union-Find
struct weighted_union_find{
    vector<ll> par;
    vector<ll> dif;
    explicit weighted_union_find(ll n):par(n,-1),dif(n){}
    ll2 find(ll u){
        vector<ll> A;
        ll dis=0;
        while(par[u]>=0){
            A.push_back(u);
            dis+=dif[u];
            u=par[u];
        }
        ll sum=dis;
        rep(i,A.size()){
            par[A[i]]=u;
            sum-=dif[A[i]];
            dif[A[i]]+=sum;
        }
        return {u,dis};
    }
    bool same(ll u,ll v){return find(u).a==find(v).a;}
    void merge(ll u,ll v,ll w){
        auto[ur,ud]=find(u);
        auto[vr,vd]=find(v);
        if(ur==vr)return;
        if(par[ur]>par[vr]){
            swap(ur,vr);
            w=-w;ud=-ud;vd=-vd;
        }
        par[ur]+=par[vr];
        par[vr]=ur;
        dif[vr]=w+ud-vd;
    }
    ll diff(ll u,ll v){return find(v).b-find(u).b;}
};
// Coordinate Compression
vector<ll> comp(const vector<ll>&A){
    ll n=A.size();
    set<ll> S;
    for(ll a:A)S.insert(a);
    vector<ll> T;
    for(ll s:S)T.push_back(s);
    vector<ll> ans(n);
    rep(i,n)ans[i]=distance(T.begin(),lower_bound(all(T),A[i]));
    return ans;
}
// MST
vector<ll3> mst(ll n,vector<ll3>&E){
    sort(all(E));
    union_find U(n);
    vector<ll3> ans;
    for(auto[w,u,v]:E){
        if(!U.same(u,v)){
            U.merge(u,v);
            ans.emplace_back(w,u,v);
        }
    }
    return ans;
}
// Bipartite Coloring
vector<ll> bip_color(const vector<vector<ll>>&G){
    ll n=G.size();
    vector<ll> ans(n,-1);
    bool ok=true;
    rep(i,n){
        if(ans[i]==-1){
            ans[i]=0;
            queue<ll> Q({i});
            while(!Q.empty()){
                ll p=Q.front();Q.pop();
                for(ll q:G[p]){
                    if(ans[q]==-1){
                        ans[q]=ans[p]^1;
                        Q.push(q);
                    }else if(ans[q]==ans[p])ok=false;
                }
            }
        }
    }
    if(!ok)ans[0]=-1;
    return ans;
}
// Lowlink
pair<vector<ll>,vector<ll>> lowlink(const vector<vector<ll>>&G,ll s){
    ll n=G.size();
    vector<ll> dis(n,-1),low(n);
    dis[s]=0;
    ll c=1;
    auto dfs=[&](auto&&dfs,ll x)->int{
        for(ll y:G[x]){
            if(dis[y]==-1){
                dis[y]=c;low[y]=c;++c;
                dfs(dfs,y);
                low[x]=min(low[x],low[y]);
            }else if(dis[y]<dis[x]-1)low[x]=min(low[x],dis[y]);
        }
        return 0;
    };
    dfs(dfs,s);
    return {dis,low};
}
// Map with Default Value
template<typename S,typename T>
struct default_map:map<S,T>{
    T def;
    explicit default_map(T def):def(def){}
    T&operator[](const S&i){return map<S,T>::emplace(i,def).first->second;}
};
// Subset Sum (制作途中)
/*
vector<ll> subset_sum(const vector<ll>&A,ll x){
    ll n=A.size(),m=*max_element(all(A));
    ll t=0,s=0;
    for(;t<n;++t){
        s+=A[t];
        if(s>=x)break;
    }
    s-=A[t];
    if(t==n)return {-1};
    vector dp(n+1,vector<ll>(2*m+1,-1));
    vector pre(n+1,vector<ll3>(2*m+1));
    dp[t][s-x+m]=t;
    repa(i,t,n+1)repr(j,2*m+1){
        if(i<n){
            if(dp[i+1][j]<dp[i][j]){
                dp[i+1][j]=dp[i][j];
                pre[i+1][j]={-1,i,j};
            }
            if(j+A[i]<=2*m&&dp[i+1][j+A[i]]<dp[i][j]){
                dp[i+1][j+A[i]]=dp[i][j];
                pre[i+1][j+A[i]]={i,i,j};
            }
        }
        repa(k,(i?dp[i-1][j]:0),dp[i][j])if(j>=A[k]&&dp[i][j-A[k]]<k){
            dp[i][j-A[k]]=k;
            pre[i][j-A[k]]={k,i,j};
        }
    }
    if(dp[n][m]==-1)return {-1};
    vector<ll> ans(n,0);
    rep(i,s)ans[i]=1;
}
*/
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    vector<ll> A(n),B(n);
    rep(i,n)cin>>A[i];
    rep(i,n)cin>>B[i];
    vector<ll> C(n,E6);
    vector<vector<ll>> X(100001);
    rep(i,n){
        auto D=divisors(A[i]);
        for(ll d:D)X[d].push_back(i);
    }
    ll s=E6*n;
    repra(i,1,100001){
        for(ll j:X[i]){
            s-=C[j];
            C[j]=min(C[j],(i-B[j]%i)%i);
            s+=C[j];
        }
        if(s<=k){cout<<i<<'\n';return 0;}
    }
}

yukicoder

結果

コンパイルメッセージ

ソースコード