- P158's solution
P158's Solution
- 2025-9-10 17:20:08 @
设取模前的答案为 。
打表可知,当 时,。
根据以上性质,我们直接对 的情况按照 暴力计算即可。
(实际上,这一性质是可以严格证明的,过程如下:)
$$\begin{aligned} x \otimes 119 &=\dfrac{119^2+2023x}{833+119x} \\ &=\dfrac{14161+2023x}{833+119x} \\ &=\dfrac{2023(7+x)}{119(7+x)} \\ &=\dfrac{2023}{119} \\ &=17 \end{aligned} $$$$\begin{aligned} f(n) &=n \otimes (n-1) \otimes (n-2) \otimes \ldots \otimes 1 \\ &=((n \otimes (n-1) \otimes (n-2) \otimes \ldots \otimes 120) \otimes 119) \otimes 118 \otimes 117 \otimes \ldots \otimes 1 \\ &=17 \otimes 118 \otimes 117 \otimes \ldots \otimes 1 \\ &\equiv 40176944 \pmod {10^8+7} \end{aligned} $$#include <bits/stdc++.h>
using namespace std;
const int P = 1e8 + 7;
int read()
{
int x = 0;
char c = getchar_unlocked();
while (c < '0') c = getchar_unlocked();
while (c >= '0')
{
x = x * 10 + c - '0';
c = getchar_unlocked();
x = min(x, 1000);
}
return x;
}
int divs(int a, int b, int p = P)
{
if (b % a == 0) return b / a;
int x = divs(p % a, a - b % a, a);
return (1ll * x * p + b) / a;
}
long long calc(long long x, long long y)
{
return divs((833 + x * y) % P, (y * y + 2023 * x) % P);
}
signed main()
{
freopen("calc.in", "r", stdin);
freopen("calc.out", "w", stdout);
int T = read();
while (T--)
{
int n = read();
int res = n;
for (int i = n - 1; i >= 1; i--)
res = calc(res, i);
cout << res << endl;
}
return 0;
}