每日“二”题
目录十年OI一场空，不开longlong见祖宗
A
题解：
最值问题，一个条件在变，考虑使用二分：
我们每次查找一个可切的最大巧克力，二分判断能不能这么切即可。
C++代码
void solve() {
int n, k, l = 1, r = 0, ans;
cin >> n >> k;
vector<pair<int, int>>qwq(n);
for(auto &x : qwq) {
cin >> x.first >> x.second;
int mx = max(x.first, x.second);
r = max(mx, r); //确定一个二分最大值，这里其实也可以给一个很大的值减少代码量
}
while(l <= r) { //二分答案
int mid = l + r >> 1;
//check() 按一般背的板子来是写一个 check() 我这里为了方便直接写这里面了
int tot = 0;
for(auto x : qwq)tot += (x.first / mid) * (x.second / mid);
if(tot < k)r = mid - 1;
//check()截止
else l = mid + 1;
}
cout << r;
}
B
题解：
我们创建一个前缀和数组，接着看一下里面同余的有几个数即可
（为什么同余就说明有倍数呢？这是因为：
如果两数之间和不为k倍数，则余数一定不同，容易可得自行证明吧XD
C++代码
void solve() {
ll n, k, i, j,ans=0;
cin >> n >> k;
vector<ll>qwq(n + 1); //前缀和数组
vector<ll>qaq(k + 1); //等效哈希表->map
for(i = 1;i <= n;++i) {
cin >> qwq[i];
//qwq[i] %= k; 这个并不重要，可以省略
qwq[i] += qwq[i - 1]; //前缀和，解题关键1
}
// 试了下暴力，并不能过
for(i = 0;i <= n;++i)ans += qaq[qwq[i] % k]++; //同余，解题关键2
cout << ans;
}