四两拨千斤,GCC编译器(同余模) - HDU 3123

对于两个数M和N,如果M%P == N%P,则可以说M和N对P同余。记作公式:

M≡N(modP)

同余这一属性看起来简单,然而却是数论中极为重要的概念。与之相关的公式和定理更是纷繁芜杂,如果不是数学背景的童鞋,恐怕很难深入去钻研所有的知识。

我们这一篇作为一个简单的入门,用同余公式来解决一个阶乘问题。在做题之前,先来熟悉一个简单的公式:

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

这个公式简单的说就是模运算的分配律,感性的可以认为,M对P的余数X,以及N对P的余数Y,两者相加X+Y可能大于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.

第一行表示测试用例个数T

后面每行包含2个整数n和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

这道题就是上面公式的典型应用,对于一个阶乘n!来说,如果m<n,则必有:n! % m = 0

也就是说,n!对所有小于等于n的数取模都是0。

数学最大的特点之一就是喜欢说废话,而且还要证明。

通过取余避免了大数运算,另外本题精巧之处还在于在一次for循环中计算了从阶乘1!、2!一直到(m-1)!的和。

本文隶属于算法合集中的一篇,更多内容可以通过菜单栏点击算法合集查看~

源代码:GCC

#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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-10-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ----1181 变形课

变形课 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java...

3176
来自专栏ACM算法日常

当七夕遇上算法竞赛

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

1432
来自专栏应兆康的专栏

100个Numpy练习【5】

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

60710
来自专栏数据结构与算法

BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

1522
来自专栏小樱的经验随笔

回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

4424
来自专栏数据结构与算法

P1510 精卫填海

题目描述 【版权说明】 本题为改编题。 【问题描述】 发鸠之山,其上多柘木。有鸟焉,其状如乌,文首,白喙,赤足,名曰精卫,其名自詨。是炎帝之少女,名曰女娃。女娃...

3447
来自专栏数据结构与算法

2843 拯救炜哥

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

2855
来自专栏应兆康的专栏

100个Numpy练习【5】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

77812
来自专栏爱撒谎的男孩

回溯算法

2743
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

1113

扫码关注云+社区

领取腾讯云代金券