D. Enormous Carpet

Codeforces

IDCF10093D

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Ameer is an upcoming and pretty talented problem solver who loves to solve problems using computers. Lately, He bought a very very very large square carpet that has an enormous area, so he stopped amazed as to how large is this carpet exactly… Unfortunately, Ameer has a small length measurement tool, so he can’t measure the area of the carpet as a whole. However, Ameer has a very smart algorithm for folding a square piece of paper reducing it to an exact fraction of its original size, and then he came up with another intelligent algorithm for measuring the area of the carpet. Ameer decided to fold the carpet N times, each time reducing it to 1/K of its remaining area, After that he would measure the remaining area of the carpet and apply his algorithm to calculate the original area. As Ameer is still a beginner problem solver he wants to check whether his algorithm is correct. Also, since the final answer might be incredibly large, Ameer wants to check the remainder of the answer over several prime numbers of his choosing. Can you help Ameer getting the correct answer so that he can compare it with his own ? For each test case, you would be given three space separated integers on the first line N, K and A respectively, Where N and K are as described earlier and A is the area that Ameer has measured after folding the carpet N times. In the second line there will be an integer number C. The third line contains C integer prime numbers where the i-th number is called Pi. After the last test case, there will be a line containing three zeroes separated by a single space. 1 ≤ N, K, A ≤ 231 1 ≤ C ≤ 100 2 ≤ Pi < 231 For each test case you should output on the first line “Case c:” where ‘c’ is the case number, then one line containing ‘C’ space separated integers on a line where the i-th integer is the remainder of the original area over Pi ## Input For each test case, you would be given three space separated integers on the first line N, K and A respectively, Where N and K are as described earlier and A is the area that Ameer has measured after folding the carpet N times. In the second line there will be an integer number C. The third line contains C integer prime numbers where the i-th number is called Pi. After the last test case, there will be a line containing three zeroes separated by a single space. 1 ≤ N, K, A ≤ 231 1 ≤ C ≤ 100 2 ≤ Pi < 231 ## Output For each test case you should output on the first line “Case c:” where ‘c’ is the case number, then one line containing ‘C’ space separated integers on a line where the i-th integer is the remainder of the original area over Pi [samples]

**Definitions** Let $ N, K, A \in \mathbb{Z}^+ $ denote the number of folds, the folding factor, and the measured area after folding, respectively. Let $ P_1, P_2, \dots, P_C $ be distinct prime moduli. **Constraints** $ 1 \leq N, K, A \leq 2^{31} $, $ 1 \leq C \leq 100 $, $ 2 \leq P_i < 2^{31} $ for all $ i \in \{1, \dots, C\} $. **Objective** Compute the original area $ A_{\text{original}} = A \cdot K^N $, and for each prime $ P_i $, output $ (A \cdot K^N) \bmod P_i $.

API Response (JSON)

{
  "problem": {
    "name": "D. Enormous Carpet",
    "description": {
      "content": "Ameer is an upcoming and pretty talented problem solver who loves to solve problems using computers. Lately, He bought a very very very large square carpet that has an enormous area, so he stopped ama",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10093D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ameer is an upcoming and pretty talented problem solver who loves to solve problems using computers. Lately, He bought a very very very large square carpet that has an enormous area, so he stopped ama...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, K, A \\in \\mathbb{Z}^+ $ denote the number of folds, the folding factor, and the measured area after folding, respectively.  \nLet $ P_1, P_2, \\dots, P_C $ be distinct prime m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments