C. Floor and Mod

题意:
给你一个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;
}
上一篇:《Modern Python Cookbook》(Python经典实例)笔记1.5 真除法和向下截断除法(floor除法)


下一篇:C - Floor and Mod(思维+贡献求枚举)