标签：right frac divisible Sum mid int include left
A. K-divisible Sum
思路
\[ans = \left \lceil \frac{kx}{n} \right \rceil
\]
\[x = x_{min} \ge \left \lceil \frac{n}{k} \right \rceil
\]
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e5+10;
const int M = 2e5+10;
int n,k;
bool check(int x){
return x >= ceil(1.0 * n / k);
}
void solve(){
int t;
cin >> t;
while(t -- ){
cin >> n >> k;
int l = 1,r = 1e9;
while(l < r){
int mid = l + r >> 1;
if(check(mid))r = mid;
else l = mid + 1;
}
cout << (int)ceil((long double)k * l / n) << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
注意
- \(k * l\)会爆int需要先转为long double
- 1e+09 != 100000000 输出时还要转回int
技巧
- 向上取整转化为向下取整
\[\left \lceil \frac{n}{k} \right \rceil =
\left \lfloor \frac{n + k - 1}{k} \right \rfloor
\]
标签：right,
frac,
divisible,
Sum,
mid,
int,
include,
left
From： https://www.cnblogs.com/J-12045/p/17211055.html