Skip to content

Instantly share code, notes, and snippets.

@SOF3
Created October 22, 2020 14:00
Show Gist options
  • Save SOF3/6d4f9c810cd895d620353a2fbc5406f9 to your computer and use it in GitHub Desktop.
Save SOF3/6d4f9c810cd895d620353a2fbc5406f9 to your computer and use it in GitHub Desktop.
#include <iostream>
// #define dbg(x) (cout << #x << ": " << x << endl, x)
#define dbg(x) 0
using namespace std;
typedef long long ll;
ll MIN(ll a, ll b) {
return a < b ? a : b;
}
ll MAX(ll a, ll b) {
return a > b ? a : b;
}
// a + a+1 + ... + b, inclusive
ll sums(ll a, ll b) {
dbg("sums");
dbg(a);
dbg(b);
return (a + b) * (b - a + 1) / 2;
}
// [l, r] closed set
ll truncatedSum(ll l, ll r, ll a) {
r += 1;
ll a2 = a * a;
if(a >= (1LL << 32)) {
a2 = 0x7FFFFFFFFFFFFFFF;
}
dbg(a);
dbg(l);
dbg(r);
if(l >= a2) {
return r - l;
}
ll top = 0;
if(a2 < r) {
top += r - a2;
}
r = MIN(a2, r);
ll low = l / a;
ll high = r / a;
dbg(low);
dbg(high);
ll low_count = MAX(0, low * (a+1) - l);
ll high_count = MIN(high, r - high * a);
dbg(low_count);
dbg(high_count);
return low_count + high_count + sums(low + 1, high - 1) + top;
}
int main() {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T; cin >> T;
while(T--) {
ll a, l, r; cin >> a >> l >> r;
auto ans = truncatedSum(l, r, a);
cout << ans << '\n';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment