同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1653_乘法逆元2

2022-5-16 18:17| 发布者: Hocassian| 查看: 48| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950481465600-Problem List-采集的数据-后羿采集器.html

Pro.ID

1653

Title

乘法逆元 2

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1653

AC

Submit

Ratio

25.00%

时间&空间限制

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

描述

这可能是一道模板题。

给定 n 个正整数 a_i ，求每个数在模 p 意义下的乘法逆元。

提示：请使用高效的读入方式。

输入

第一行一个整数 n 。 1 ≤ n ≤ 5000000

第二行 n 个整数 a_i

1 ≤ a_i ≤ p , p = 10⁹+7

输出

Description

这可能是一道模板题。

给定 n 个正整数 a_i ，求每个数在模 p 意义下的乘法逆元。

提示：请使用高效的读入方式。

Input

第一行一个整数 n 。 1 ≤ n ≤ 5000000

第二行 n 个整数 a_i

1 ≤ a_i ≤ p , p = 10⁹+7

Output

一行一个数，表示

Sample Input

5
4
7
8
12
123456

Sample Output

650798912

Hint

五个数的逆元分别是：

250000002

142857144

125000001

83333334

78351802

样例输入