#P3481. DZY Loves Math III

    ID: 2693 传统题 1000ms 512MiB 尝试: 543 已通过: 88 难度: 8 上传者: 标签>难度分类提高+/省选-数论中国剩余定理线性同余方程Miller–RabinPollard–Rho快速乘防溢出快速幂组合数学乘法原理CF2400By

DZY Loves Math III

DZY Loves Math III

题目描述

给定整数 P,QP,Q,求满足

xy≡Q(modP),0≤x<P,0≤y<Pxy\equiv Q\pmod P,\qquad 0\le x<P,\quad 0\le y<P

的整数有序对 (x,y)(x,y) 的数量。

输入格式

先读入整数 nn,随后依次读入 nn 个整数 p1,…,pnp_1,\ldots,p_n,再读入 nn 个整数 q1,…,qnq_1,\ldots,q_n。整数之间用空白分隔。

题目中的 P=∏i=1npiP=\prod_{i=1}^n p_i,Q=∏i=1nqiQ=\prod_{i=1}^n q_i。

输出格式

输出一行一个整数,表示方案数对 109+710^9+7 取模的结果。

样例 #1

3
1 2 3
2 4 2
6

此时 P=6P=6,Q=16Q=16。六组解为 (1,4)(1,4)、(2,2)(2,2)、(2,5)(2,5)、(4,1)(4,1)、(4,4)(4,4)、(5,2)(5,2)。

数据范围

1≤n≤101\le n\le 10,1≤pi≤10181\le p_i\le 10^{18},0≤qi≤10180\le q_i\le 10^{18},P≥2P\ge 2。

原赛共有 44 组测试,总时限 55 秒,内存限制 64 MB64\ \mathrm{MB}。

原题面 PDF