C. Floor and Mod

https://codeforces.com/contest/1485/problem/C

题意

给出x和y,求出满足 \(1<=a<=x, 1<=b<=y, a / b = a mod b\) 条件的\((a,b)\)数量(此处 \(/\) 指的是向下取整，下同).

思路

设 \(k = a / b\), 则有 \(a = k * b + k\), 即: \(a = k * (b + 1)\),所以 \(b = a / k - 1\).
因为 \(k < b\), 所以 \(a > k * (k + 1)\),即: \(k < {sqrt}(a)\),
所以我们只需要枚举 \(k(1 <= k <= {sqrt}(x))\) ,对于每一个 \(k\):

对应的b最小值为 \(k + 1\), 因为 \(b > k\).
对应的b的最大值为 \(min(y, x / k - 1)\) ,因为 \(a\)的上限为 \(x\).
所以对于当前k来说,对答案的贡献为 \(min(y, x/ k - 1) - k\).

所以枚举k即可得出答案。

Code

/*---------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（′<_｀ ）　 
　　　　 （ ′_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__?つ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　?
--------------------------------------------------------------*/
#include<bits/stdc++.h>
#define IO  ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define req(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back		
#define fi first
#define se second
#define PI pair<int,int>
#define PII pair<ll,PI>

using namespace std;

typedef long long ll;
const int N=1e5+7;
const ll mod=1e9+7;

int main()
{
	IO; 
	int t;
	cin>>t;
	while(t--){
		ll x,y;
	    cin>>x>>y;
	    ll ans=0,k=1;
	    while(k<=y&&k*(k+1)<=x){
	        ans+=min(y,x/k-1)-k;
	        k++;
	    }cout<<ans<<endl;
	}
	return 0;
} 

C. Floor and Mod ——(Codeforces Round #701 (Div. 2))