[HUSTFC 2023] 新取模运算

Luogu

IDLGP9774

Time1000ms

Memory256MB

DifficultyP4

2023O2优化高校校赛

在这道题中，我们定义一个新的运算符号 $\oplus$ 并将其称为新取模运算。当计算 $x \oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\oplus 5=4$，$20\oplus 5=4$，$100\oplus 5=4$。给定一个质数 $p$，接下来会有多组询问，对于每次询问会给出一个整数 $n$，你需要计算出 $n!\oplus p$ 的值。其中 $n!$ 是 $n$ 的阶乘，即所有小于等于 $n$ 的正整数的乘积。 ## Input 第一行包含两个整数 $T\ (1\le T\le 10^5)$ 和 $p\ (2\le p\le 10^6)$，分别表示询问的次数和给定的质数。接下来 $T$ 行，每行包含一个整数 $n\ (1\le n\le 10^{18})$，含义如题目所述。 ## Output 对于每次询问，输出一行包含一个整数，即 $n!\oplus p$ 的值。 [samples]

Samples

Input #1

Output #1

4
1
2

Input #2

2 10007
1919
810

Output #2

3152
3679

API Response (JSON)

{
  "problem": {
    "name": "[HUSTFC 2023] 新取模运算",
    "description": {
      "content": "在这道题中，我们定义一个新的运算符号 $\\oplus$ 并将其称为新取模运算。 当计算 $x \\oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\\oplus 5=4$，$20\\oplus 5=4$，$10",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9774"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在这道题中，我们定义一个新的运算符号 $\\oplus$ 并将其称为新取模运算。\n\n当计算 $x \\oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\\oplus 5=4$，$20\\oplus 5=4$，$10...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments