思路:
假设⌊ba⌋=amodb=k
那么显然k是小于b的。
a=k∗b+k=k∗(b+1)
k2<k∗(b+1)=a≤x
所以1≤k≤x,k的范围就确定了
接下来只需枚举k,看有多少对符合的数即可。
整理上面的条件可得:
b>k
1≤b≤y
1≤k∗(b+1)≤x=>1≤b≤kx−1
这样枚举的时候,对于每一个k,b和k的值确定了,a的值也就确定了。所以答案就等于枚举的时候b的取值方案数求和,即:
k=1∑xmax(0,min(y,kx−1)−k
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7; void solve(){ ll x=read(),y=read(); ll res=0; for(ll k=1;k*k<=x;k++) res=res+max(0ll,min(y,x/k-1)-k); printf("%lld\n",res); } int main(){ int T=read(); while(T--) solve(); return 0; }
参考:官方题解