Submission #41856992

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
ll T,n,m,r;

ll S(ll n){return n*(n+1)/2;}
ll f(ll a,ll b,ll c,ll n){
	if(n<0)return 0;
	if(n==0)return a/c;

	if(a>=c || b>=c){
		return (a/c) * (n+1) + (b/c) * S(n) + f(a%c,b%c,c,n);
	}
	ll m = (a+n*b)/c;
	return n*m - f(c-a-1,c,b,m-1);
}

ll p[35];

void solve(){
	cin>>n>>m>>r;

	ll ans = 0;
	rep(i,0,30){
		p[i] = f(r,m,1<<i,(n-r)/m);
	}
	rep(i,0,30){
		ans += (p[i] - 2*p[i+1]);
	}
	cout<<ans<<"\n";
}

int main(){
	cin>>T;
	while(T--)solve();

    return 0;
}

Submission Info

Judge Result