题目

来源：https://www.luogu.com.cn/problem/B2133

我家住在一条短胡同里，这条胡同的门牌号从 $1$ 开始顺序编号。

若其余各家的门牌号之和减去我家门牌号的两倍，恰好等于 $n$ ，求我家的门牌号及总共有多少家。数据保证有唯一解。

输入 $n$ 。要求程序输出两个正整数，分别是我家的门牌号及总共有多少家，中间用单个空格隔开

样例：

输入
100
样例输出
12 16

分析

这道题目的定位是入门。而且 $n$ 的范围很小，所以可以直接暴力枚举，所有的题解也的确是这样干的。

我们假设总数为 $x$ ，我家的门牌号为 $y$ ，那么有

\frac{x(x+1)}{2}-y-2y=n

显然这道题就去枚举符合这个式子的 $x$ 和 $y$ 。

但换一个角度，我们将这个式子展开：

6y=x^2+x-2n

而且 $y$ 又是整数，这就说明 $(x^2+x-2n)\%6=0$

也就是说，一元二次方程 $x^2+x-2n=0$ 在 $mod6$ 数域上有解。

这样我们就能得到 $mod6$ 数域上的解 $x_6$

那么整数域上 $x$ 的数值就可以表示为 $x=x_6+6k,k\in Z$

又因为 $y>0$ ，因此 $6y=x^2+x-2n>0$

将 $x=x_6+6k$ 带入上式，就能求得 $k$ 的最小值，也就能求出 $y$ 的数值。

解答

1.在`mod6`域上求解一元二次方程

我们仍然可以使用二次函数的求根公式，只是需要我们在mod6域上实现这些运算。

$x^2+x-2n=0$

求根公式很容易写出：

x=\frac{-1\pm\sqrt{1+8n}}{2}

由于模域（严格来说，这只是环）上只实现了加法和乘法，所以我们需要自己实现其他运算。

平方根就是求平方的逆运算，我们首先考虑求平方。
而除二就是乘二的逆运算，我们也先求乘二。

$x$	$x^2$	$2\times x$
0	0	0
1	1	2
2	4	4
3	3	0
4	4	2
5	1	4

根据上表，我们能很容易地写出逆运算（找逆元：注意逆元可能存在多个）

$x$	$\sqrt{x}$	$x/2$
0	0	0 or 3
1	1 or 5	无效
2	无效	1 or 4
3	3	无效
4	2 or 4	2 or 5
5	无效	无效

但，，，这样看起来上述方程就有8个解了。其实不然，由于代数基本定理，一元二次方程最多只会有2个解。

其实，我们只需要在这三个多值运算符中，只取一个为正真的多值就好了就可以了(*)。也就是说对于 $\pm$ 只取 $+$ ，对于 $\sqrt{\quad}$ 也只取第一个值，只留下 $x/2$ 运算作为真正产生多值的。

(*):我没有严格证明，多试了几次发现没问题，就拿来用了。。。。

好了，现在我们就有了两个解 $x_{6(1)}$ 、 $x_{6(2)}$

2.求解整数域上的 $x$

求解下述不等式，我们同样也使用求根公式

x^2+x-2n>0,x=x_6+6k

解得

k>\frac{\pm\sqrt{1+8n}-(2x_6+1)}{12}

显然 $k\geq 0$ 且是整数，因此

k=\lfloor\frac{\sqrt{1+8n}-(2x_6+1)}{12}\rfloor+1

我们再将 $k$ 带回上式就能求得 $y$ 了。

3.验证解的正确性

由于有两个解，而题目又保证了唯一性，我们就可以先尝试一个解，如果正确就输出。
若不正确，我们就尝试另一个解。

容易写出如下验证公式

\text{verify}(x,y,n)=\left\{\begin{aligned} &6y==x^2+x-2n &\text{when }1\leq y\leq x\\ &\text{false} &\text{others} \end{aligned}\right.

代码

#include <exception>
#include<stdio.h>
#include<cmath>

int sqrt_mod6(int x) {
    if (x==1) {
        return 1;
    }
    if (x==3) {
        return 3;
    }
    throw std::exception();
}
int div2_mod6_first(const int x) {
    if (x==2) {
        return 1;
    }
    if (x==4) {
        return 2;
    }
    if (x==0) {
        return 0;
    }
    throw std::exception();
}
int div2_mod6_second(const int x) {
    if (x==2) {
        return 4;
    }
    if (x==4) {
        return 5;
    }
    if (x==0) {
        return 6;
    }
    throw std::exception();
}
int mod6(int a) {
    int result = a % 6;
    if (result < 0) {
        result += 6;
    }
    return result;
}
int k_min(const int x6, const int n) {
    const int delta=1+8*n;
    const auto value=(sqrt(delta)-(2*x6+1))/12;
    return floor(value+1);
}
int verify(int x,int y,int n) {
    if (1<=y&&y<=x) {
        return x*(x+1)/2-3*y==n;
    }
    return false;

}
int main() {
    int n=100;
    scanf("%d",&n);


    int temp=(1+8*mod6(n))%6;
    int sqrt_root=sqrt_mod6(temp);


    int temp2=mod6(-1-sqrt_root);
    int x6=div2_mod6_first(temp2);
    int x6_2=div2_mod6_second(temp2);

    //printf("%d %d",x1,x2);
    int k_1=k_min(x6,n);


    int x_1=x6+6*k_1;
    int y_1=(x_1+x_1*x_1-2*n)/6;
    bool valid=verify(x_1,y_1,n);
    if (valid) {
        printf("%d %d",y_1,x_1);
    }else{
        int k_2=k_min(x6_2,n);
        int x_2=x6_2+6*k_2;
        int y_2=(x_2+x_2*x_2-2*n)/6;
        printf("%d %d",y_2,x_2);
    }


    return 0;
}