题解：[P11184 带余除法]

题解：P11184 带余除法

题意

\(T\) 组测试数据，给定有余数除法中的被除数（\(n\)）和商（\(k\)），求余数的不同可能性数量。

数据规模与约定

对于全体数据，保证 \(1 \le T \le 10,1 \le n \le 10^{14},0 \le k \le 10^{14}\)。

算法 tag

数学

题解

暴力肯定会 TLE，得想一种最好是 \(O(1)\) 的算法来优化。

根据有余数除法的性质，可以得到 \(n=kq+r\)，\(n\) 是被除数，\(r\) 是余数。而且应该保证 \(0 \le r < q\)，把 \(0 \le r < q\) 和 \(n=kq+r\) 结合起来，可以得出 \(q \in [\lfloor \frac{n}{k+1} \rfloor +1 , \lfloor \frac{n}{k} \rfloor]\)

具体推导：

\[\because 0 \le r < q,n=kq+r\\ \therefore 0 \le n-kq \Longrightarrow kq \le n \Longrightarrow q \le \lfloor \frac{n}{k} \rfloor \\n-kq<q \Longrightarrow n<q(k+1) \Longrightarrow q>\lfloor \frac{n}{k+1} \rfloor \Longrightarrow q \ge \lfloor \frac{n}{k+1} \rfloor +1\\\therefore q \in [\lfloor \frac{n}{k+1} \rfloor +1 , \lfloor \frac{n}{k} \rfloor] \]

所以，\(r\) 的不同可能性数量为 $\max (0,\lfloor \frac{n}{k} \rfloor-(\lfloor \frac{n}{k+1} \rfloor+1)+1)= \max(0,\lfloor \frac{n}{k} \rfloor - \lfloor \frac{n}{k+1} \rfloor) $

特别的，数据范围中 \(0 \le k \le 10^{14}\) 说明 \(k\) 会有等于 \(0\) 的情况，所以当 \(k=0\) 时，答案为 \(1\)，因为商为 \(0\) 时，只要除数 $> $ 被除数，商为 \(0\) ，余数为除数，所以只有一种可能。

Code

在放代码之前，请注意数据范围，还是那句话：十年 OI 一场空，不开 long long 见祖宗。

#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl '\n'
/*====================*/
void Solve()
{ll n,k;cin>>n>>k;if(k==0){cout<<1<<endl;return;}cout<<n/k-n/(k+1)<<endl; 
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;cin>>T;while(T--)Solve();return 0;
}