# 四两拨千斤，GCC编译器（同余模） - HDU 3123

M≡N(modP)

(M+N)%P=(M%P+N%P)%P(M+N)%P=(M%P+N%P)%P

Problem Description

The GNU Compiler Collection (usually shortened to GCC) is a compiler system produced by the GNU Project supporting various programming languages. But it doesn’t contains the math operator “!”. In mathematics the symbol represents the factorial operation. The expression n! means "the product of the integers from 1 to n". For example, 4! (read four factorial) is 4 × 3 × 2 × 1 = 24. (0! is defined as 1, which is a neutral element in multiplication, not multiplied by anything.) We want you to help us with this formation: (0! + 1! + 2! + 3! + 4! + ... + n!)%m

gcc编译器是GNU项目组的开发的一个编译系统，支持多种编程语言。但是gcc不支持阶乘符号!。对于表达式n!，它表示从1乘到n的一个值。比如4! = 4x3x2x1 = 24。0的阶乘为1，表示不乘以任何值。

Input

The first line consists of an integer T, indicating the number of test cases. Each test on a single consists of two integer n and m.

Output

Output the answer of (0! + 1! + 2! + 3! + 4! + ... + n!)%m. 输出 (0! + 1! + 2! + 3! + 4! + ... + n!)%m.

Constrains 0 < T <= 20 0 <= n < 10^100 (without leading zero) 0 < m < 1000000

Sample Input

1
10 861017

Sample Output

593846

#include <stdio.h>
#include <stdint.h>

int main()
{
int count;
scanf("%d", &count);

int64_t ans;
int64_t futher, num, mod;

char nstr[200];

while (count--)
{
scanf("%s", nstr);
scanf("%I64d", &mod);

//公式： (a+b)%c=(a%c+b%c)%c
//可以知道 m！+（m+1)！….n!这一些对m取余都是0，所以就不需考虑了。
//所以判断n和m的大小，取较小值。
if (strlen(nstr) >= 7)
num = 1000000;
else
sscanf(nstr, "%I64d", &num);

if (num > mod)
num = mod;

futher = 1;
ans = 1;

for (int i = 1; i <= num; i++)
{
futher = (futher * i) % mod;
//如果能够整除mod，说明后面的数都可以整除mod，不需要再计算
if (futher == 0)
break;
//每次将模加入到ans中
ans += futher;
}

printf("%I64d\n", ans % mod);
}
return 0;
}

212 篇文章32 人订阅

0 条评论

## 相关文章

3176

### 当七夕遇上算法竞赛

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去T...

1432

### 100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一，非常适合刚学习完Numpy基础的同学，完成以下习题可以帮助你更好的掌握这个基础库。

60710

1522

4424

3447

### 2843 拯救炜哥

2843 拯救炜哥 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有一天，炜...

2855

77812

2743

1113