A. An Olympian Math Problem (数论) [2018 ACM-ICPC Nanjing Online Contest]

Description

Alice, a student of grade 66, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:

We denote k!k!:

k!=1×2××(k1)×kk! = 1 \times 2 \times \cdots \times (k - 1) \times k

We denote SS:

S=1×1!+2×2!++S = 1 \times 1! + 2 \times 2! + \cdots +
(n1)×(n1)!(n - 1) \times (n-1)!

Then SSmodulenn is ____________

You are given an integer nn.

You have to calculate SSmodulonn.

Input

The first line contains an integer T(T1000)T(T \le 1000), denoting the number of test cases.

For each test case, there is a line which has an integer nn.

It is guaranteed that 2n10182 \le n\le 10^{18}.

Output

For each test case, print an integer SSmodulonn.

Hint

The first test is: S=1×1!=1S = 1\times 1!= 1, and 11modulo 22 is11.

The second test is: S=1×1!+2×2!=5S = 1\times 1!+2 \times 2!= 5, and 55modulo33 is22.

Sample Input

1
2
3
2
2
3

Sample Output

1
2
1
2

题解

首先,显然有 S=k=1n1kk!=k=1n1((k+1)!k!)=n!1S = \sum\limits_{k=1}^{n-1}k \cdot k! = \sum\limits_{k=1}^{n-1}((k+1)!-k!)=n!-1.

S  mod  nS \; \mathrm{mod} \; n

=(n!1)  mod  n= (n! - 1) \; \mathrm{mod} \; n

$ = (n! + n - 1) ; \mathrm{mod} ; n$

$ = n! ; \mathrm{mod} ; n + (n - 1) ; \mathrm{mod} ; n$

$ = n - 1$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int t = 0;
cin >> t;

while(t--) {
ll n = 0;
cin >> n;
cout << n - 1 << endl;
}

return 0;
}