#1157520 (C++17) No.3516 Very Large Range Mod

• 問題: No.3516 Very Large Range Mod
• ユーザー: Yoyoyo8128
• 提出日時: 2026-04-17 01:56:43
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 152 ms / 2,000 ms
• コード長: 3,792 bytes
• コンパイル時間: 1,966 ms
• コンパイル使用メモリ: 221,284 KB
• 実行使用メモリ: 8,064 KB
• 最終ジャッジ日時: 2026-04-24 20:55:37
• 合計ジャッジ時間: 7,694 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

#pragma region Yoyoyo

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using i128t=__int128_t;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const long long inf=1ll<<60;
const string Yes="Yes";
const string No="No";
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define faster ios::sync_with_stdio(false);cin.tie(nullptr);
#define print(s) cout<<s<<endl;

template<typename T>
inline bool chmax(T &a,T b){return ((a<b)?(a=b,true):(false));}
template<typename T>
inline bool chmin(T &a,T b){return ((a>b)?(a=b,true):(false));}
template<typename T>
ll sum(const T&a){return accumulate(all(a),0LL);}

template<typename T,typename U>
istream &operator>>(istream &is,pair<T,U>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U>&p){
    os<<p.first<<' '<<p.second;
    return os;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(auto &x:v)is>>x;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<(i?" ":"")<<v[i];
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<T>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<v[i]<<endl;
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<vector<T>>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<"i = "<<i<<endl;
        os<<v[i];
    }
    return os;
}

#ifdef LOCAL
template<class... Args>
void debug_out(Args... args){
    int _i=0;
    ((cerr<<(_i++?", ":" ")<<args), ...);
    cerr<<"\n";
}
#define debug(...){\
    cerr<<"["<<#__VA_ARGS__<<"]:";\
    debug_out(__VA_ARGS__);\
}
#else
#define debug(...)
#endif

#pragma endregion Yoyoyo


long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}


int main(){
    faster;
    ll N,K,M;
    cin>>N>>K>>M;
    vector<ll>B(N),C(N);
    cin>>B>>C;
    {
        assert(1<=N && N<=200000);
        assert(1<=K && K<=1000000000 && 1<=M && M<=1000000000);
        for(int i=0;i<N;i++){
            assert(1<=B[i] && B[i]<=1000000000 && 1<=C[i] && C[i]<=1000000000);
        }
    }
    vector<ll>rui(N+1,0);
    for(int i=0;i<N;i++)rui[i+1]=rui[i]+B[i];
    ll now=0;
    {
        ll K2=K;
        for(int i=0;i<N;i++){
            now+=C[i]*min(K,B[i]);
            K-=min(K,B[i]);
            now%=M;
        }
        K=K2;
    }
    ll idx=0;
    ll ans=0;
    if(!now)ans++;

    while(idx+K<rui[N]){
        auto itr1=upper_bound(all(rui),idx);
        auto itr2=upper_bound(all(rui),idx+K);
        ll nex=min(((*itr1)-(idx)),((*itr2)-(idx+K)));

        ll sa=0;
        {
            sa-=C[distance(rui.begin(),itr1)-1];
            sa+=C[distance(rui.begin(),itr2)-1];
            sa%=M;
            while(sa<0)sa+=M;
        }

        if(sa==0){
            if(now==0)ans+=nex;
            idx+=nex;
            continue;
        }

        ll g=gcd(M,sa);
        ll per=M/g;
        if(gcd(g,now)==g){
            ll x,y;
            extGCD(sa,M,x,y);
            x%=per;
            x*=(M-now)/g;
            x%=per;
            while(x<=0)x+=per;
            ll ko=(nex-x)/per+1;
            if(nex<x)ko=0;
            ans+=ko;
        }

        idx+=nex;
        now+=sa*nex;
        now%=M;

    }
    
    cout<<ans<<"\n";
    
}