Submission #37863204

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

// \sum_{x=0}^n \lfoor \frac{ax+b}{c} \rfloor
ll floor_sum(ll a,ll b,ll c,ll n){
  if(a==0) return (b/c)*(n+1);
  if(a >= c or b >= c) return n*(n+1)/2*(a/c) + (n+1)*(b/c) + floor_sum(a%c,b%c,c,n);
  ll m = (a*n+b)/c;
  return m*n - floor_sum(c,c-b-1,a,m-1);
}

int main(){
  int t=read();
  while(t--){
    int n=read();
    int m=read();
    int r=read();
    ll ans=0;
    rep(p,0,30){ // 2^30 > 10^9
      // = sum((value+2^p)/(2^{p+1}) - (value)/(2^{p+1}))
      ans += floor_sum(m,r+(1<<p),1<<(p+1),(n-r)/m);
      ans -= floor_sum(m,r       ,1<<(p+1),(n-r)/m);
    }
    printf("%lld\n",ans);
  }
  return 0;
}

Submission Info

Compile Error

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

Judge Result