带余除法
题目背景
注意：提交至洛谷时，请使用标准输入输出，而非文件输入输出。
NOTICE: When submitting your code on Luogu site, please use standard IO instead of file IO.
Click here (or at the bottom of this page) to download the English version of statements (PDF).
注意：本次比赛所有题目的大样例均为 Linux 换行符格式，在 Windows 系统内可能无法正常显示换行。
题目描述
我们已经学过带余除法。对于两个正整数 \(n,q\)，如果 \(n\) 除以 \(q\) 的商为 \(k\)，余数为 \(r\)，我们可以写出带余除法算式 \(n\div q = k \cdots\cdots r\)，或被记为 \(n\div q = k (\text{r. } r)\)。本题中，为了简化，哪怕 \(r=0\)，我们也要写出这个余数。
现在有一个带余除法，然而你只知道被除数 \(n\) 和商 \(k\)，而并不知道除数 \(q\) 和余数 \(r\)。你想知道余数有多少种可能。
输入格式
本题有多组测试数据。输入的第一行有一个正整数 \(T\)，表示数据组数。
之后 \(T\) 行，每行有一个正整数 \(n\) 和自然数 \(k\)，分别表示带余除法的被除数和商。
输出格式
对于每组测试数据，输出一行一个自然数，表示余数的不同可能性数量。
样例 #1
样例输入 #1
2
10 2
1 0
样例输出 #1
2
1
样例 #2
样例输入 #2
参见 division/division2.in
样例输出 #2
参见 division/division2.ans
提示
【样例 1 解释】
对于第一组数据，被除数为 \(10\)，商为 \(2\)。
- 如果除数是 \(1,2,3\)，那么商分别是 \(k=10,5,3\)，不符合题意。
- 如果除数是 \(4\)，那么商为 \(2\)，余数为 \(r=2\)。
- 如果除数是 \(5\)，那么商为 \(2\)，余数为 \(r=0\)。
- 如果除数是 \(6,7,8,9,10\)，那么商都是 \(1\)，不符合题意。
- 如果除数 \(>10\)，那么商为 \(0\)，不符合题意。
对于第二组数据，被除数为 \(1\)，商为 \(0\)。
只要除数 \(q>1\)，那么 \(1\div q = 0 \cdots\cdots 1\) 一定是正确的带余除法算式。余数只有 \(1\) 这一种可能。
【数据范围】
对于前 \(30\%\) 的数据，保证 \(1\le n\le 1000\)，\(0\le k\le 1000\)。
另有 \(20\%\) 的数据，保证 \(k\le 10^5\)。
另有 \(20\%\) 的数据，保证 \(k\ge 10^9\)。
对于全体数据，保证 \(1\le T\le 10\)，\(1\le n\le 10^{14}\)，\(0\le k\le 10^{14}\)。
思路
-
观察题目列出\(n\div q=k \cdots\cdots r ( r < k )\)
-
求余数有多少种可能，就是求除数有多少可能
-
则q最小为\(n \div (k+1)+1\)
-
q最大为\(n \div k\)
-
最终结果为q的最大值-q的最小值+1
代码
点击查看AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long n,k;
cin>>n>>k;
if(k==0) cout<<1<<endl;
else{
long long l=n/(k+1)+1;
cout<<n/k-l+1<<endl;
}
}
return 0;
}