TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

37.5% (3/8)

Submission's AC Ratio

5.8% (8/138)

Tags

Description

顜立猿是一個充滿好奇心的新興人猿,他時常在這個世界到處走訪,每每走訪到一個角落他就會利用各種社群軟體紀錄下他的生活點滴,然而最近的他卻越來越少在社群軟體中發布新的訊息。

擅長跟蹤小蘿莉與新興人猿的你注意到了這件事,經過漫長的分析與調查,你發現最近他似乎喜歡上了許多小蘿莉,並且獲得了許多有關蘿莉的相關情報,然而為了規避FBI(Fake Business Institute)的調查,有關蘿莉的資訊總是被使用一種神祕的方式隱藏了起來。

為了盡速看到顜立猿的新訊息,你偷偷竊取了相同的蘿莉資訊,並打算將這些資訊一點一滴的揭露給顜立猿知道,可惜你並沒有如同「智慧之神──喌檗斔」般聰明的腦袋。難過的你只好向喌檗斔祈求一點提示讓你能順利解開被隱藏起來的資訊,但是「智慧之神──喌檗斔」的時間是有限的,對於一組蘿莉的資訊他最多只願意提示$100$次,因次你需要審慎選擇你所想知道的提示資訊。

又經過一系列的研究後,你發現一個蘿莉的資訊可以用一個非負整數$P$來表示,而你獲得的被隱藏的資訊是由三個非負整數$C, e, N$構成,並且我們知道$C \equiv P^ e \pmod{N} $且$N$可以唯一的被分解成兩個質數$X, Y$的相乘(也就是$N = XY, X \in \mathbb{P} \land Y \in \mathbb{P} $),此外你每次可以詢問「智慧之神──喌檗斔」一個$x$,祂將會回答你$ ( x \mod{\varphi(N)} ) \mod{K} $(其中$\displaystyle \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$)。

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#include "lib2078.h"#include <cinttypes>之後實作下列函數,如果你的函數名稱不對或者長得不像下面那行,你將有機會獲得一個CE。
uint64_t decrypt( uint64_t e, uint64_t N, uint64_t C, uint64_t k );
此函數之參數如題目敘述之定義,並且該函數將須回傳$P$。
另外在同一組測資內,這個函數有機會被呼叫多達5000次,所以請確保你的函式有進行初始化,並且足夠有效率。

同時你將可以呼叫一個函數 uint64_t PhiOracle( uint64_t x ),代表你向「智慧之神──喌檗斔」詢問了$x$一次。

注意:如果你在程式裡實作了main()函式,你也會獲得一個CE。

那些條件們:
$ 0 < P, C, N, e < 2^ {62}, 1 \leq K \leq 100$
$ e < \varphi(N), P < N, C < N$
$ \varphi(N) \not\equiv 0 \pmod{k}, gcd( e, \varphi(N) ) = 1 $

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Sample Input

Sample Output

Hints

子任務分數輸入限制
0~3 10 $N\leq 200$
4~7 20 $N\leq10^ 6$
8~11 20 $N\leq10^ {12}$
12~15 3 $P^ e < N$
16~19 47 無額外限制

Problem Source

problem set by oToToT
problem adapted from 2019 AIS3 pre-exam Crypto RSA101

Subtasks

No. Testdata Range Score
1 0~3 10
2 4~7 20
3 8~11 20
4 12~15 3
5 16~19 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 2500 65536 65536 3
9 2500 65536 65536 3
10 2500 65536 65536 3
11 2500 65536 65536 3
12 1000 65536 65536 4
13 1000 65536 65536 4
14 1000 65536 65536 4
15 1000 65536 65536 4
16 1000 65536 65536 5
17 1000 65536 65536 5
18 1000 65536 65536 5
19 1000 65536 65536 5