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

• 問題: No.3516 Very Large Range Mod
• ユーザー: yu23578
• 提出日時: 2026-04-16 23:17:46
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 307 ms / 2,000 ms
• コード長: 3,393 bytes
• コンパイル時間: 1,878 ms
• コンパイル使用メモリ: 229,376 KB
• 実行使用メモリ: 34,384 KB
• 最終ジャッジ日時: 2026-04-24 20:55:11
• 合計ジャッジ時間: 10,456 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

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

ソースコード

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

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

ll _abs(ll X){
    if(X <= 0) return -X;
    else return X;
}

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(){
    string _N, _K, _M; cin >> _N >> _K >> _M;
    ll N = parse(_N), K = parse(_K), M = parse(_M);
    
    vector<ll> B(N),C(N);
    for(ll i = 0; i < N; i++){
        string b; cin >> b;
        B[i] = parse(b);
    }
    for(ll i = 0; i < N; i++){
        string c; cin >> c;
        C[i] = parse(c);
    }
    
    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, next_idx - now_idx);
        S += (r - l) * (next_idx - now_idx);
    }
    cout << answer << "\n";
}