• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

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

admin

11月 28, 2021

题意:

[sumlimits_{a=1}^x sumlimits_{b=1}^y[lfloorfrac{a}{b}floor=a\%b ]
]

法一:

将a改写为kb+r,注意到(k=lfloordfrac{a}{b}floor)(r=a\%b),即k=r

所以a=k(b+1),且r<b,即k<b

所以每个k的贡献区间为(dfrac{min(x,b^2-1)}{b+1})

分两段算,当(b^2-1<=x)时,答案是(sum(b-1)),可以用等差数列求和直接做

(x<b^2-1)时,这是形如(sumlfloordfrac{x}{b+1}floor)的求和式,使用整除分块即可(O(sqrt n))处理

#include<bits/stdc++.h>
#define int long long
using namespace std;

int rd(){
	int ret=0, f=1;char c;
  	while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  	while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  	return ret*f;
}

void solve(){
	int x,y;
	int ans=0;
	x=rd();y=rd();
	int up=1;
	while(up*up-1<x&&up<=y) up++;
	ans+=(up-1)*(up-2)/2;
	for(int l=up+1,r;l<=y+1;l=r+1){
		int v=x/l;
		if(v==0) break;
		r=min(y+1,x/v);
		ans+=v*(r-l+1);	
	}
	printf("%lld
",ans);
}

signed main(){
	int T=rd();
	while(T--) solve();
  	return 0;
}

法2

注意到(kle sqrt x),采用枚举k的方式,我们求b的个数

刚刚的(k(b+1)le x)可变形为(ble dfrac{x}{k}-1),同时还有(ble y)

(k=r<b),这是左边界

因而每个k对答案的贡献为((k,min(dfrac{x}{k}-1,y)])

(O(sqrt x))枚举k,求和即可

#include<bits/stdc++.h>

using namespace std;
#define int long long

int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0', c=getchar();
  return ret*f;
}

int x,y;

void solve(){
  x=rd();y=rd();
  int up=(int)(sqrt(x)+0.5),ans=0;
  for(int k=1;k<=up;k++)
    ans+=max(0ll,min(x/k-1,y)-k);
  cout<<ans<<endl;
}

signed main(){
  int T=rd();
  while(T--) solve();
  return 0;
}

本文来自博客园,作者:GhostCai,转载请注明原文链接:https://www.cnblogs.com/ghostcai/p/15111138.html

发表回复

您的电子邮箱地址不会被公开。