#P13630. [ARC172E] Last 9 Digits

    ID: 12832 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-模数逐层提升欧拉定理二项式定理模逆元快速幂

[ARC172E] Last 9 Digits

题目描述

判断是否存在正整数 nn,使得 nnn^n 除以 10910^9 的余数等于 XX,如果存在,求出最小的 nn。对于给定的 QQ 个测试用例,请分别输出答案。

输入格式

输入以如下格式从标准输入读入。对于第 ii 个测试用例 (1≤i≤Q)(1 \leq i \leq Q),XX 的值为 XiX_i。

QQ
X1X_1
X2X_2
⋮\vdots
XQX_Q

输出格式

请输出 QQ 行,第 ii 行输出第 ii 个测试用例的答案。如果不存在满足条件的 nn,输出 −1-1。

输入输出样例 #1

输入 #1

2
27
311670611

输出 #1

3
11

说明/提示

限制条件

  • 1≤Q≤100001 \leq Q \leq 10000
  • 1≤X≤109−11 \leq X \leq 10^9 - 1
  • XX 不是 22 的倍数,也不是 55 的倍数
  • 所有输入均为整数

样例解释 1

本输入样例包含 22 个测试用例。

  • 第 11 个:33=273^3 = 27,2727 除以 10910^9 的余数是 2727,所以 n=3n = 3 满足条件。
  • 第 22 个:1111=28531167061111^{11} = 285311670611,285311670611285311670611 除以 10910^9 的余数是 311670611311670611,所以 n=11n = 11 满足条件。