[EPXLQ2024 fall round] Simple Math Problem

ID: 10757

远端评测题

1500ms

512MiB

难度: 5

上传者:

说明

Cute_QiQi 有一个可爱的整数 $n$ 。

现在，Cute_QiQi 想知道有多少个 $m \in (0,n)$ ，满足 $nm$ 能被 $n-m$ 整除。

本题单个测试点内有多组测试数据。

第一行一个整数 $T$ ，表示数据组数。

以下 $T$ 行，每行一个整数 $n$ 。

输出 $T$ 行，每行一个整数表示答案。

2
114
1919

13
4

当 $n = 114$ 时，可有 $m \in \{38,57,76,78,95,96,102,105,108,110,111,112,113\}$。

当 $n = 1919$ 时，可有 $m \in \{1558,1818,1900,1918\}$ 。

本题采用捆绑测试与子任务依赖。

设 $p$ 为 $n$ 质因数分解后最大的质数， $p,q$ 均为质数。

$\text{Subtask}$	$n \le$	特殊性质	分值	依赖子任务
$0$	$10^{14}$	$n = p$	$2$
$1$	$10^3$		$7$
$2$	$10^6$		$11$	$1$
$3$	$10^9$		$24$	$1,2$
$4$	$10^{14}$	$n = pq$	$12$
$5$		$p \le 10^6$	$15$
$6$			$29$	$0,1,2,3,4,5$

对于所有数据， $1 \le n \le 10^{14}, 1 \le T \le 10$ 。