题解：P11184 带余除法

yummy · 2024-10-16 11:29:10 · 题解

A. 带余除法 (division) 官方题解

本题考查的主要知识点有：

• 【1】代数（初中部分）
• 【2】for 语句、if 语句、输入输出语句

首先特判 k=0，此时答案为 1。当 k>0 时，每个 q 都对应一个 r，讨论 q 的个数：

考虑带余除法的定义，n=kq+r。代入 0\le r < q 可得 kq\le n < kq+q。换言之，\dfrac{n}{k+1}<q\le \dfrac{n}{k}。

当 q 为整数时，它等价于 \lfloor \dfrac{n}{k+1}\rfloor<q\le \lfloor \dfrac{n}{k}\rfloor，只要输出 \lfloor \dfrac{n}{k}\rfloor-\lfloor \dfrac{n}{k+1}\rfloor 即可。

#include<bits/stdc++.h>
using namespace std;
long long T,n,k;
int main(){
    for(cin>>T;T;T--){
        cin>>n>>k;
        if(k!=0)cout<<n/k-n/(k+1)<<endl;
        else cout<<1<<endl;
    }
    return 0;
}