[CodeForces1485C]Floor And Mod

discription:
How many pairs \(<a,b>\), s.t. \(a\mod b=\lfloor\frac{a}{b}\rfloor\), for \(1\leqslant a\leqslant x\), $1\leqslant b\leqslant y $ ?
solution:
\(a\mod b= \lfloor \frac{a}{b}\rfloor\)
\(a-\lfloor\frac{a}{b}\rfloor b = \lfloor\frac{a}{b}\rfloor\)
\(a=(b+1)\lfloor\frac{a}{b}\rfloor\), and \(0\leqslant\lfloor\frac{a}{b}\rfloor<b\)

And don‘t forget:
\(1\leqslant a\leqslant x, 1\leqslant b\leqslant y\)

\(\Rightarrow\)How many pairs a,b in the range above, \(s.t.\ a=q(b+1), q\leqslant b-1\)

if \(\forall b\in[1,y],i.e. \frac{x}{b+1}\geqslant b-1\), only \((b-1)\) numbers of divisor of \(x\) ;
else \(i.e.\frac{x}{b+1}< b-1\), two parts of ans, firstly the same as \(\uparrow\), then,without the \(\le(b-1)\) restriction.

A.P. and Number Theory div_blocks, we AC this problem.

code:

#include<cstdio>
#include<cmath>
typedef long long ll;
int main() {
	int T; scanf("%d", &T);
	while(T--) {
		int x, y; scanf("%d%d", &x, &y);
		int p = (int)sqrt(x + 1);
		if (y <= p) {
			printf("%d\n", y * (y - 1) >> 1);
			continue;
		}
		ll ans = p*(p-1) >> 1;
		++y;// b+1 --> y+1
		for (int l = p + 2; l <= y;) {
			int t = x / l;
			if (!t) break;// avoid RE.
			int r = x / t;
			if (y < r) r = y;// minimum right bound
			ans += (r - l + 1) * t;
			l = r + 1;
		}
		printf("%lld\n", ans);
	}
}

[CodeForces1485C]Floor And Mod

原文：https://www.cnblogs.com/dwt2021/p/14439033.html