結果

問題 No.3516 Very Large Range Mod
コンテスト
ユーザー yu23578
提出日時 2026-04-16 06:59:23
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 2,475 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,223 ms
コンパイル使用メモリ 225,832 KB
実行使用メモリ 18,972 KB
最終ジャッジ日時 2026-04-24 20:53:39
合計ジャッジ時間 15,368 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = (a >= 0 ? 1 : -1);
        y = 0;
        return a >= 0 ? a : -a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

tuple<ll,ll,ll,ll,bool> solve(ll a, ll b, ll c) {
    ll x, y;
    ll g = extgcd(a, b, x, y);

    if (c % g != 0) {
        return {0, 0, 0, 0, false};
    }

    ll mul = c / g;
    ll x0 = x * mul;
    ll y0 = y * mul;

    ll d = b / g;
    ll f = -a / g;

    return {d, x0, f, y0, true};
}

ll _ceil(ll a, ll b){
    if(b <= -1){b *= -1; a *= -1;}
    if(a >= 0){
        if(a % b == 0) return a / b;
        else return a / b + 1;
    }
    else{
        if(abs(a) % b == 0) return -(abs(a) / b);
        else return -(abs(a) / b);
    }
}

ll _floor(ll a, ll b){
    if(b <= -1){b *= -1; a *= -1;}
    if(a >= 0) return a / b;
    else{
        if(abs(a) % b == 0) return - (abs(a) / b);
        else return - (abs(a) / b + 1);
    }
}

ll count_k(ll a, ll b, ll c, ll X){
    auto [d,e,f,g,flag] = solve(a,b,c);
    
    if(!flag) return 0;
    
    e--; X--;
    if(d == 0){
        if(0 <= e && e <= X) return 1;
        else return 0;
    }
    else if(d <= -1){
        d *= -1; e *= -1;
        return _floor(-e, d) - _ceil(-X - e, d) + 1;
    }
    else{
        return _floor(X - e, d) - _ceil(-e, d) + 1;
    }
}

int main(){
    ll N, K, M; cin >> N >> K >> M;
    vector<ll> B(N),C(N);
    for(ll i = 0; i < N; i++) cin >> B[i];
    for(ll i = 0; i < N; i++) cin >> C[i];
    
    vector<tuple<ll,ll,ll>> query;
    ll ruiseki = 0;
    for(ll i = 0; i < N; i++){
        query.push_back({ruiseki, 1, C[i]});
        query.push_back({ruiseki - K, 2, C[i]});
        ruiseki += B[i];
    }
    query.push_back({0, 3, -1}); query.push_back({ruiseki - K, 4, -1});
    sort(query.begin(),query.end());
    
    ll answer = 0, l = 0, r = 0, S = 0;
    for(ll i = 0; i < query.size(); i++){
        auto [now_idx, query_type, x] = query[i];
        if(query_type == 1) l = x;
        if(query_type == 2) r = x;
        if(query_type == 3){
            answer = 0;
            if(S % M == 0) answer++;
        }
        if(query_type == 4) break;
        
        ll next_idx = get<0>(query[i + 1]);
        answer += count_k(-(r - l), M, S % M, next_idx - now_idx);
        S += (r - l) * (next_idx - now_idx);
    }
    cout << answer << "\n";
}
0