题面

Description

小象同学在初等教育时期遇到了一个复杂的数学题,题目是这样的:给定自然数 $n$ ,确定关于 $x,y,z$ 的不定方程

$\sqrt{x-\sqrt{n}} + \sqrt{y} - \sqrt{z}=0$ 的解。

当时的小象同学并不会做这道题。多年后,经过高等教育的洗礼,小象同学发现这道题其实很简单。小象同学认为你一定也会做这道题,所以把这道题留给了你。为了便于输出,你不需要输出每一组解 $(x,y,z)$ ,你只需要给出解的数量和所有解的 $xyz$ 之和对 $(10^{9}+7)$ 取模的值即可。注意,解的数量不对 $10^{9}+7$ 取模。

Input

输入包含多组测试数据。输入的第一行包含一个正整数 $T\;(1 \leq T \leq 10^{4})$ ,表示测试数据的组数。接下来依次描述每组测试数据,对于每组测试数据:

仅一行,包含一个非负整数 $n\;(0\leq n \leq 2 \times 10^{9})$ ,含义如题面所示。

Output

对于每组数据,输出一行。若方程有无穷多组自然数解,则在这一行输出 $\text{‘‘infty''}$(不含引号),否则在这一行输出两个整数,其中第一个整数表示方程的解数,第二个整数 表示所有解的 $xyz$ 之和对 $(10^{9}+7)$ 取模的值,这两个整数之间用恰好一个空格隔开,行末不要有多余的空格。

Sample Input

3
6
12
24

Sample Output

0 0
1 12
2 72

Hint

当 $n=12$ 时,方程唯一的解为 $x=4,y=1,z=3$ 。

当 $n=24$ 时,方程的两组解为 $x=5,y=2,z=3$ 和 $x=7,y=1,z=6$ 。

题解

首先注意到显然当且仅当 $n=0$ 或 $n$ 为完全平方数时,给定方程有无穷多组解,通解为 $(\sqrt{n},c,c)$ ,其中 $c$ 是任意自然数。

现在,考察何时方程有有限多组解。将所给方程做如下变换

$$ \sqrt{x-\sqrt{n}}=\sqrt{z}-\sqrt{y} $$

两边平方得

$$ x-\sqrt{n}=y+z-2\sqrt{yz} $$

移项得

$$ x-(y+z)=\sqrt{n}-2\sqrt{yz} $$

此时,考虑两种情况:

  • 方程左右两边均为 $0$

此时,显然有

$$ \left \{ \begin{matrix} x=y+z \\ n = 4yz \end{matrix} \right. $$

  • 方程左右两边均不为 $0$

因为 $x,y,z\in \mathbb{N} $ ,故 $x-(y+z) \in \mathbb{Z}$ ,故应当也有 $\sqrt{n}-2\sqrt{yz} \in \mathbb{Z}$ 。若 $n \neq 4yz$ ,则当且仅当 $n$ 与 $yz$ 均为 $0$ 或完全平方数(但不同时为 $0$ )时,满足该条件;这是不可能的。因为,若 $n$ 或 $yz$ 为 $0$ 时,必有 $n=yz=0$;若 $n$ 或 $yz$ 均不为 $0$ ,则 $n$ 必须为完全平方数,此时方程有无穷多组解。

综上,当且仅当 $\left \{ \begin{matrix} x=y+z \\ n=4yz \end{matrix} \right.$ 成立时,方程有有限多组解。

此时注意到当且仅当 $n$ 是 $4$ 的倍数时,方程有解;又注意到 $n \leq 2 \times 10^{9}$ ,因此遍历 $[1, \sqrt{n}]$ 寻找 $n$ 的因子即可。时间复杂度 $O(\sqrt{n})$ 。

注意此题long long会超时

代码

#include <bits/stdc++.h>
using namespace std;

const int MODULO = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 0;
    cin >> t;

    while (t--) {
        int n = 0;
        cin >> n;

        if (n == 0 || (int)sqrt((double)n) * (int)sqrt((double)n) == n) {
            cout << "infty" << endl;
            continue;
        }

        if (n % 4) {
            cout << 0 << " " << 0 << endl;
            continue;
        }

        n /= 4;
        int m = (int)sqrt((double)n + 0.5);

        int ans = 0, num = 0;
        for (int i = 1; i <= m; i++) {
            if (n % i)
                continue;

            num++;

            int z = n / i;
            int x = ((long long)i + z) % MODULO;
            ans   = ((long long)ans + (long long)x * n % MODULO) % MODULO;
        }

        cout << num << " " << ans << endl;
    }

    return 0;
}

preView