Description
You are given a recurrent formula for a sequence
f:
f(
n) = 1 +
f(1)
g(1) +
f(2)
g(2) + … +
f(
n−1)
g(
n−1),
where
g is also a recurrent sequence given by formula
g(
n) = 1 + 2
g(1) + 2
g(2) + 2
g(3) + … + 2
g(
n−1) −
g(
n−1)
g(
n−1).
It is known that
f(1) = 1,
g(1) = 1. Your task is to find
f(
n) mod
p.
Input
The input consists of several cases. Each case contains two numbers on a single line. These numbers are
n (1 ≤
n ≤ 10000) and
p (2 ≤
p ≤ 2·10
9). The input is terminated by the case with
n =
p = 0 which should not be processed. The number of cases in the input does not exceed 5000.
Output
Output for each case the answer to the task on a separate line.
Sample Input
| input | output |
| 1 22 110 0 | 12 |
题目在吓唬人啊，仔细算一算这个就是阶乘啊。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int n, p;
while (cin >> n >> p, n, p)
{
long long tot = 1;
for (int i = 1; i <= n; i++) tot = tot*i%p;
cout << tot << endl;
}
return 0;
}