提出 #49589945

---

ソースコード 拡げる

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}

// ax+by=c, gcd(a,b) = 1, return {x,y}
// ((a/b)*b+a%b) x + by = c
// b (y+(a/b)x) + (a%b) x = c
tuple<ll,ll> exgcd(ll a,ll b,ll c){
  if(b == 0) return {c/a, 1};
  auto [_x,_y] = exgcd(b,a%b,c);
  return {_y,_x - (a/b) * _y};
}
ll mod(ll a,ll b){return (a%b+b)%b;}
// a = kb + [0,b) return k
ll floordiv(ll a,ll b){ return (a-mod(a,b))/b; }
// a = kb + (-b,0] return k
ll ceildiv(ll a,ll b){ return (a-mod(a,b))/b + int(mod(a,b) != 0); }
// count( (x,y) \in[1,n])
// ax+by=c
ll solve(ll a,ll b,ll c,ll n){
  if(c <= 0) return 0;
  ll m = gcd(a,b);
  if(c % m != 0) return 0;
  a/=m;
  b/=m;
  c/=m;
  auto [x,y] = exgcd(a,b,c); // gcd(a,b) = 1
  // (x+kb,y-ka)
  // 1 <= x+kb <= n
  // 1 <= y-ka <= n
  // (1-x)/b <= k <= (n-x)/b
  // (y-n)/a <= k <= (y-1)/a
  ll maxk = min(floordiv(n-x,b),floordiv(y-1,a));
  ll mink = max(ceildiv(1-x,b),ceildiv(y-n,a));
  auto bound=[&](ll v){return 1<=v and v<=n;};
  while(mink <= maxk and (!bound(x+mink*b) or !bound(y-mink*a))) mink++;
  while(mink <= maxk and (!bound(x+maxk*b) or !bound(y-maxk*a))) maxk--;
  return maxk >= mink ? maxk-mink+1:0;
}

int main(){
  // ai + bj + ck = x
  // count( (i,j,k) \in [1,n])
  ll n = read(); // 1e6
  ll a = read(); // [1,1e9]
  ll b = read(); // [1,1e9]
  ll c = read(); // [1,1e9]
  ll x = read(); // [1,3e15]

  ll m = gcd(gcd(a,b),gcd(c,x));
  a/=m;
  b/=m;
  c/=m;
  x/=m;

  ll ans = 0;
  rep(i,1,n+1) ans += solve(b,c,x-a*i,n);
  printf("%lld\n",ans);
  return 0;
}
// 非常质朴的一道题
// 很有gcd/exgcd的想法
// a,b,c,x
// 就暴力for i,然后exgcd没了??

提出情報

コンパイルエラー

Main.cpp: In function ‘ll read()’:
Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果