问题 C: Congruences

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

Your task is to solve a system of $m$ congruences, each one represented in the following format:

$x^{p_{i}} \equiv q_{i} (mod n) (i = 1, 2, ..., m)$

Here, $p_{i}$ refers to pairwise distinct prime numbers, $n$ is the product of all $p_{i}$ (i.e., $n = \prod_{i = 1 m} p_{i}$ ), and $q_{i}$ is an integer within the range of $[0, n)$ .

The goal is to find the smallest positive integer $x$ that fulfills all given congruences. If there is no solution exists for the given system of congruences, output $- 1$ .

The first line contains a positive integer $T$ ( $1 \leq T \leq 1 0^{4}$ ), indicating the number of test cases.

For each test case, the first line contains a positive integer $m$ , and each of the following $m$ lines contains two integers $p_{i}$ and $q_{i}$ ( $2 \leq p_{i} \leq 1 0^{18}$ , $0 \leq q_{i} < n$ ). It is guaranteed that $n = \prod_{i = 1 m} p_{i} \leq 1 0^{18}$ .

For each test case, output a single positive integer

x

representing the answer or output

- 1

5
3
4

You can use __int128 in your C++ code

2023HDU多校1003

问题 C: Congruences

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签

问题 C: Congruences

题目描述

输入格式

输出格式

输入样例 复制

输出样例 复制

数据范围与提示

分类标签

输入样例复制

输出样例复制