ABC 165 D - Floor Function

ABC 165 D - Floor Function

Question

$f\left(x\right)=floor\left(Ax/B\right)-A\times floor\left(x/B\right)$f(x)=floor(Ax/B)−A×floor(x/B)
求 $x\le n$x≤n使得 $f(x{)}_{max}$f(x)max​求 $f(x{)}_{max}$f(x)max​

Solution

1. 三分法。当时打的时候盲猜这是一个先递增后递减的函数，故可以采用三分法。然而实际上这是一个关于B为周期的函数，并不满足严格三分的条件。问了下大佬，说随机数据的情况下，刚好被周期卡住的概率很小，所以能过。我感觉这个虽然具有周期性，但是会往同一个周期收敛，虽然在不同周期但是可以看做同一个周期。（我口胡瞎说的，不会严格证明，就直觉吧？）
2. $f\left(x\right)=f(x+B)$f(x)=f(x+B)，且在 $x\in [0,B-1]$x∈[0,B−1]上 $f\left(x\right)$f(x)单调递增。
   证明：设 $xmodB=t$x mod B=t， $\lfloor \frac{x}{B}\rfloor =k$⌊Bx​⌋=k， $\lfloor \frac{Ax}{B}\rfloor =Ak+\lfloor \frac{At}{B}\rfloor$⌊BAx​⌋=Ak+⌊BAt​⌋，故 $f\left(x\right)=\lfloor \frac{At}{B}\rfloor$f(x)=⌊BAt​⌋，显然 $f\left(x\right)$f(x)在 $t\in [0,B-1]$t∈[0,B−1]上单调递增，故 $x=min(B-1,n)$x=min(B−1,n)为最佳选择。

Code1.1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll a,b,n;

ll check(ll x){
	return (a*x)/b-a*(x/b);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>n;
	ll L=1,R=n;
	while(R>L){
		ll m1=L+(R-L)/3;
		ll m2=R-(R-L)/3;
		if(check(m1)>check(m2))
			R=m2-1;
		else
			L=m1+1;
	}
	cout<<check(L)<<'\n';
	return 0;
}

Code1.2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll a,b,n;

ll check(ll x){return (a*x)/b-a*(x/b);}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>n;
	ll L=1,R=n;
	while(R-L>10){
		ll m1=L+(R-L)/3;
		ll m2=R-(R-L)/3;
		if(check(m1)>check(m2))
			R=m2-1;
		else
			L=m1+1;
	}
	ll mx=0;
	for(ll i=L;i<=min(n,R);i++){
		if(check(i)>mx){
			mx=check(i);
		}
	}
	cout<<mx<<'\n';
	return 0;
}

Code2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a, b, n;
	cin>>a>>b>>n;
	n=min(n, b-1);
	cout<<a*n/b<<endl;
	return 0;
}