IPSC 2018 Problem E – Encrypted romance

IPSC 2018

Problem E – Encrypted romance

Alice and Bob are two young lovers who frequently send each other hearts and kisses over the Internet. However, they (rightfully) suspect that Eve might be interested in hearing all their private messages. Alice and Bob are both untouched by modern cryptography, so they have designed their own encryption scheme. As you probably already expect, it’s not that good.

In order to be “extra secure”, Alice and Bob have chosen n different symmetric ciphers. Whenever one of them wants to send a message to the other, he or she splits it into n pieces (called blocks) and encrypts each block using a different cipher.

Of course, they need some secret keys in order to do all that encryption and decryption. On the last day of summer Alice and Bob picked one shared secret key k. The key k was then used to compute the keys k_i used for the individual ciphers.

Eve has intercepted a message Alice sent to Bob. Eve already knows all ciphers they use, and also the way in which they compute the keys k_i from the original key k. The only information she’s missing is the key k itself.

Estimate Eve’s chances of successfully decrypting at least one block of the message!

Problem specification

The secret key is an integer k between 0 and p − 1, inclusive, where p is a prime number.

The blocks of each message are numbered 1 through n. The key Alice and Bob use to encrypt and decrypt block i is denoted k_i. The key k_i was computed from k using the following formula:
$$ k_i = ((a_i \cdot k + b_i) \bmod p ) \bmod m_i$$

Luckily for our two lovers, Eve is also woefully bad at cryptography. When everything she tried failed, she decided that she will simply try finding the right k using brute force.

You are given all parameters of the encryption scheme, including the secret key k that Eve does not know. Estimate the number of keys from the key space that allow Eve to decrypt at least one block of the message.

Formally, you are asked for the number of integers k′∈[0, p) that have the following property: For at least one i ∈ {1, 2, …, n} we have $k_i = ((a_i \cdot k' + b_i) \bmod p ) \bmod m_i$. (In words, if Eve uses the key k′ instead of the correct key k, she will correctly decrypt at least one block of the message.)

Since the number of such keys may be very large, we are only interested in a rough approximation of the correct number. (Refer to the output specification.)

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case begins with a line consisting of three integers p, k and n, where

p is the prime number specifying the size of the keyspace.
k is the secret key selected by Alice and Bob.
n is the number of blocks in a message.

Then n lines follow, each describing the key generation scheme for one block of the plaintext. Each line contains three space-separated integers a_i, b_i, m_i that are used in the formula to compute the key k_i.

In both subproblems we have 1 ≤ n ≤ 100 and 0 ≤ k < p.

In both subproblems we also have ∀i ∈ {1, 2, …, n}: 1 ≤ a_i < p, 0 ≤ b_i < p, and 1 ≤ m_i ≤ p.

In the easy subproblem E1 we have t = 400, p ≤ 10⁹ and ∀i ∈ {1, 2, …, n}:m_i ≤ 1000.

In the hard subproblem E2 we have t = 100 and p ≤ 10¹⁰⁰.

Output specification

For each test case, output a single line with a floating-point number m: the amount of keys k′ from the key space that share at least one block encryption key with the actual key k.

Make sure that your output contains at least four most significant decimal digits of m (but preferably print more). The value of m may be printed in scientific notation (“1.2345678E-90”).

In the easy subproblem E1 your answer will be accepted if the relative error is at most 10⁻¹.

In the hard subproblem E2 your answer will be accepted if the relative error is at most 10⁻².

Example

Input:

4

13 10 2
2 0 5
3 1 6

19 18 2
3 4 8
2 2 6

1632899 12351 5
12453 232 789
73829 112 650
11234 893 998
788920 128492 706
123892 99109 551

5228506301 5128935514 5
516969294 4322317375 63664
65456316 100106652 423344
121168466 121978447 442230
616682668 556300002 185418
1631488462 1712350840 628094

Output:

In the first sample, we have:

$k_1 = ((2 \cdot k + 0) \bmod 13) \bmod 5 = 2$
$k_2 = ((3 \cdot k + 1) \bmod 13) \bmod 6 = 5$.

The set of useful keys is {1, 6, 10, 12}, as for k′∈{1, 6} we correctly decrypt the first block and for k′=12 we correctly decrypt the second block.

In the second sample, the key k = 18 leads to k₁ = 1 and k₂ = 0. There are five good keys: 2, 5, 8, 17, 18. Even though with k′=8 Eve deciphers both blocks correctly, the value 8 is only counted once.

In the third case, any answer in the range [10315, 12607] would be accepted for the easy subproblem. For the hard subproblem, only values within the range [11347, 11575] would be considered correct.