BZoj 2186 [Sdoi2008]沙拉公主的困惑 (1~N！中与M！互质的数的个数)

灰太狼 2022-08-25 01:42 57阅读 0赞

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2186

本题参考了：http://blog.csdn.net/acdreamers/article/details/19068791

学到了一种新的求乘法逆元的方法，博文推导中不明白的地方也在评论中得到了解答~

#include <cstdio>
    #include <bitset>
    using namespace std;
    #define i64 long long
    const int N = 10000005;
    
    bitset<N> prime;
    int mod;
    i64 fac[N],ans[N];
    i64 inv[N];
    
    void Init ()
    {
    	int i,j;
    	prime.set();
    	for (i=2; i<N; i++) if (prime[i])
    		for (j=i+i;j<N;j+=i)
    			prime[j] = false;
    
    	fac[0]=1;      //阶乘
        for (i=1;i<N;i++)
            fac[i]=fac[i-1]*i %mod;
        inv[1]=1;    //逆元
        for (i=2;i<N;i++)
        {
            if(i >= mod) break;
            inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        }
        ans[1]=1;
        for (i=2; i<N; i++)
            if (prime[i])
            {
                ans[i] = ans[i-1] * (i - 1) % mod;
                ans[i] = ans[i] * inv[i % mod] % mod;
            }
            else
                ans[i] = ans[i-1];
    }
    
    int main ()
    {
        int T;
        scanf("%d%d",&T,&mod);
    	Init ();
        while(T--)
        {
    		int m,n;
            scanf("%d%d",&n,&m);
            i64 res=fac[n]*ans[m]%mod;
            printf("%lld\n",res);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 n个数求前m个数的大小

一、描述 n个数求前m个数的大小二、分析堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效

布满荆棘的人生/ 2023年12月31日 07:20/ 0 赞/ 32 阅读

相关欧拉函数：求小于等于n且与n互质的数的个数

求小于等于n且与n互质的数的个数互质穷举法 1. 互质：两个数互质代表两者最大公约数为1 2. 最大公约数求法：辗转相除法，最小公倍数：较大值除以最大公约数乘

た入场券/ 2023年10月01日 18:48/ 0 赞/ 31 阅读

相关有N个数，个数向后移m个位置，然后把前面m个数变成最前面的m个数

有N个数，个数向后移m个位置，然后把前面m个数变成最前面的m个数 include<stdio.h> //实现移动向后移动M 个位置，然后最后面的m个

超、凢脫俗/ 2023年07月18日 09:40/ 0 赞/ 24 阅读

相关打印n个数中任意m个数组合

消除k的二进制数的最后一个1： k = k & (k-1); 计算x的二进制数的最后一个1： lowbit(x) = x & -x; include <i

绝地灬酷狼/ 2023年02月25日 03:39/ 0 赞/ 33 阅读

相关从n个数中选取m个数的所有组合

题目： ![在这里插入图片描述][2020060421241697.png] n个数1,2,...,n，从这n个数中任意选m个数，输出所有不同组合，共有C(n,

蔚落/ 2023年02月15日 10:03/ 0 赞/ 33 阅读

相关 BZoj 2186 [Sdoi2008]沙拉公主的困惑 (1~N！中与M！互质的数的个数)

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2186 本题参考了：http://blog.csdn.net/ac

灰太狼/ 2022年08月25日 01:42/ 0 赞/ 58 阅读

相关 ♥BZOJ 2190: [SDOI2008]仪仗队【欧拉函数】

2190: \[SDOI2008\]仪仗队 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 2298 Solved:

淩亂°似流年/ 2022年07月29日 08:48/ 0 赞/ 142 阅读

相关从1到m随机n个数

以下代码实现从1到m，随机n个数 public static int[] random(int m, int n) { Random r =

快来打我*/ 2022年06月15日 07:48/ 0 赞/ 216 阅读

相关编程题：从n个数中选取m个数，计算m个数的和s，判断剩余n-m个数中是否存在等于s的数，如果存在，输出最大值

描述：从n个数中选取m个数，计算m个数的和s，判断剩余n-m个数中是否存在等于s的数，如果存在，输出最大值。第一行输入n和m值，第二行输入n个数，输出最大值。例如：输入

分手后的思念是犯贱/ 2022年05月28日 11:13/ 0 赞/ 212 阅读

相关求n个数中前m个大的数的堆排序版本

堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效率比较高的。 heapsort()

小咪咪/ 2022年04月17日 06:13/ 0 赞/ 187 阅读