小明最喜欢的食堂窗口

校园编程挑战赛

题目描述

山东交通学院的食堂窗口一共有x个，是从1 到x编号的。小明说他最喜欢的食堂窗口是第y号，其他所有的食堂窗口编号加起来减去y，正好等于z。告诉你z是多少，请你计算出小明最喜欢的食堂窗口是几号，以及山东交通学院一共有多少食堂窗口。

输入格式

输入共一行，一个正整数z，输入数据保证有解。

输出格式

输出共一行，包含两个正整数，分别是小明最喜欢的食堂窗口编号及总共有多少个食堂窗口，中间用一个空格隔开。

输入输出样例

输入 #1

100

输出 #1

10 15

说明/提示

【样例解释】共 15 个食堂窗口，小明最喜欢的窗口号是 10，其余食堂窗口的编号之和是 110， 110-10=100

• 对于 40%的数据: x不超过 1000；
• 对于 70%的数据: x不超过 10000；
• 对于 100%的数据: x不超过 40000，z<2000000000

思路解析

由题意可列

$\left\{ \begin{aligned} 1 \leqslant y \leqslant x \\ z=\frac{\mathrm{x (x+1)}}{\mathrm{2}} - 2y \end{aligned} \right.$

既得

$\left\{ \begin{aligned} x^2+x-(2z+4) \geqslant 0\\ x^2-3x-2z \leqslant 0 \end{aligned} \right.$

最后，x取整数交集A，并计算出对应y，当且仅当y为整数时符合题意。

代码实现

import java.util.Scanner;

/**
 * 1<=y<=z
 * z=(x+1)x/2-2y
 */
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long z = cin.nextLong();
        //求解集
        double m1 = (-1.0 + Math.sqrt(1 + 8 * z + 16)) / 2.0;
        double m2 = (-1.0 - Math.sqrt(1 + 8 * z + 16)) / 2.0;
        double n1 = (3.0 + Math.sqrt(9 + 8 * z)) / 2.0;
        double n2 = (3.0 - Math.sqrt(9 + 8 * z)) / 2.0;
        //取整数交集
        int m1_int = (int) Math.ceil(m1);
        int n1_int = (int) Math.floor(n1);
        int m2_int = (int) Math.floor(m2);
        int n2_int = (int) Math.ceil(n2);
        //判断当x，z带入时，是否y是个整数
        for (; m1_int <= n1_int; m1_int++) {
            if ((m1_int * (m1_int + 1) / 2 - z) % 2 == 0) {
                long y = (m1_int * (m1_int + 1) / 2 - z) / 2;
                System.out.println(y + " " + m1_int);
            }
        }
        for (; n2_int <= m2_int; n2_int++) {
            if ((n2_int * (n2_int + 1) / 2 - z) % 2 == 0) {
                long y = (n2_int * (n2_int + 1) / 2 - z) / 2;
                System.out.println(y + " " + m1_int);
            }
        }
        cin.close();
    }
}