题解 P6511 【Quark and Equations】

vectorwyx · 2020-05-04 13:42:03 · 题解

附：方程化简那块LaTeX炸了……但在博客里显示的是正常的，我也不知道为啥……还请大家多多包容/kel，您如果有需要可以移步博客，感谢谅解！

以下是原文：

考场上花了2h才推出式子，我太菜了/kel

一.前置知识：

令\lfloor a \rfloor表示对a向下取整，\lceil a \rceil表示对a向上取整。则有：

对于一个小数部分不为0的浮点数a，若a的整数部分为k，则\lfloor a \rfloor=k，\lceil a \rceil=k+1。
对于一个小数部分等于0的浮点数a，\lfloor a \rfloor=\lceil a \rceil=a
对于一个浮点数a，若\lfloor a \rfloor=k，那么a的取值范围为k\le a <k+1，若\lceil a \rceil=k，那么a的取值为k-1<a\le k

二.推导式子

题目的要求是求出方程\lfloor \frac{i}{j}\rfloor+\lceil \frac{j}{i} \rceil=m且i+j=n的正整数解的个数。

那好办，把这个方程转化成不等式不就行了。

第一个方程有两个变化量：\lfloor \frac{i}{j}\rfloor和\lceil \frac{j}{i} \rceil，它们之间的关系并不明朗。如果能把两个化简成一个那该多好啊。

如何化简呢？不难发现i<j时\lfloor \frac{i}{j} \rfloor=0，而i\ge j时\lceil \frac{j}{i}\rceil=1。也就是说不管i,j谁大谁小，总是有一个变化量的值是可以确定的。因此这个方程就愉快地化简成了：

\begin{cases} 0+\lceil\frac{j}{i}\rceil=m&(i<j)\\ \lfloor\frac{i}{j}\rfloor+1=m&(i\ge j) \end{cases}

至此，我们的任务就是求解\lceil \frac{j}{i} \rceil=m和\lfloor \frac{i}{j}\rfloor=m-1

根据前置知识中的第3条，\lceil \frac{j}{i} \rceil=m可转化为不等式m-1<\frac{j}{i}\le m，把i用n-j代替，解出来就是\frac{n}{m+1}\le i<\frac{n}{m}，由于i是正整数，所以这个不等式等价于\lceil\frac{n}{m+1}\rceil\le i<\lceil\frac{n}{m}\rceil，故方程的正整数解有\lceil\frac{n}{m}\rceil-\lceil\frac{n}{m+1}\rceil个

同理，另一个方程\lfloor \frac{i}{j}\rfloor=m-1通过上述做法可以得出正整数解有\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m+1}\rfloor个

（就只是变了一下数值和取整的方向，不再赘述qwq）

综上，对于每组n,m，其答案为\lceil\frac{n}{m}\rceil-\lceil\frac{n}{m+1}\rceil+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m+1}\rfloor。

最后特判一下特殊情况，直接输出，这题就做完了。

三.代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)//宏定义简化for循环 
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){//快读 
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

void work(){//求解 
    int n=read(),m=read(),ans=0;
    //很好想的特判不多说 
    if(m>n||m==1){
        puts("0");
        return;
    } 
    if(m==n-1||m==n){
        puts("1");
        return;
    }
    int x,y;//取值范围 
    x=ceil(n*1.0/(m+1)),y=ceil(n*1.0/m);//化简后得到的第一个不等式 
    ans+=y-x;
    x=floor(n*1.0/(m+1)),y=floor(n*1.0/m);//化简后得到的第二个不等式 
    ans+=y-x;
    printf("%d\n",ans);
    return;
}

int main(){
    int T=read(); 
    while(T--) work();
    return 0;
}

码LaTeX不易，如果这篇文章给予了您帮助，您看能不能点个赞再走？谢谢！