問題一覧 > 教育的問題

No.8056 Prime Factorization with a Quantum Computer Easy

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 19
作問者 : Ryuhei Mori / テスター : tatyam
お気に入りにしたユーザー ProblemId : 3892 / 自分の提出
問題文最終更新日: 2020-02-05 11:58:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given an integer $N$ that is the product of two distinct odd primes $P$ and $Q$. Output $P$ and $Q$. However, you have access to a quantum computer and can query the order of $A$ modulo $N$ for a positive integer $A$ less than $N$ that is coprime to $N$.

Here, for an integer $N\ge 2$ and a positive integer $A$ coprime to $N$, the order of $A$ modulo $N$ is the smallest positive integer $R$ satisfying $A^R \equiv 1 \mod N$.

Input and Output

The first line of the input is given as

$N$

$N$ is a positive integer less than $2^{1024}$, and it is guaranteed to have exactly two distinct odd prime factors. When you query a positive integer $A$ less than $N$ that is coprime to $N$, the order of $A$ modulo $N$ is given as input. The format of a question query is 

? A
. If you query an $A$ that does not satisfy the conditions, your submission is judged as incorrect. The format of an answer query is 
! P Q
. It is judged as correct if $P, Q > 1$ and $PQ = N$ are satisfied. There is no limit on the number of queries, but you must output the two distinct prime factors of $N$ within the time limit, which includes the response time of the queries.

Sample

Sample 1
Input
15
1
4
2
4
4
2
4
2
Output
? 1
? 2
? 4
? 7
? 8
? 11
? 13
? 14
! 3 5

The order of 1 modulo 15 is 1, the order of 2 is 4, $\cdots$. The prime factors of 15 are 3 and 5.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。