题意:
给你一个x,y来限制a,b范围,1<=a<=x,1<=b<=y
。让你在x,y范围内a和b,有几对a/b向下取整等于amod(余)b。
思路:
我首先在草稿纸上画出了一些范围然后发现了规律。
3 4
4 3 8 3
5 4 10 4 15 4
6 5 12 5 18 5 24 5
7 6 14 6 21 6 28 6 35 6
我们设第一列左边数是left,右边是right
首先第一层都是left=right+1
。
第二层是left=right*2+2
。
第三层是left=right*3+3
。
…
所以
第n层则是left=right*n+n
。
然后遍历按照从左到右列的遍历顺序遍历。累加每列小于x的数。
复杂度:根号n。
代码:
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<math.h>
#include<vector>
#include<bitset>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e6+10;
int t;
ll x,y;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
cin>>t;
while(t--){
cin>>x>>y;
if(x>=3||y>=2){
ll ans=0,cnt=min(x-2,y-1);//asn是求答案,cnt是第一列有多少个数
ll last_num=(1+cnt),cen=1;//last_num是第一列right数字,cen是当前在累加第几列。
while(cnt&&cen*(cen+2)<=x){//累加范围当cnt列数存在,并且该列第一个数字小于x
if(last_num*cen+cen<=x) ans+=cnt;//如果该列最后一个数字都小于x则该列所有数字都可以被算上
else ans+=(x-cen*(cen+2))/cen+1;//否则就算加上前x该数字
cen++,cnt--;
}
cout<<ans<<endl;
}else cout<<0<<endl;//否则就输出0
}
return 0;
}