[SDOI2008]沙拉公主的困惑 线性筛 素数+欧拉
本文为博主原创文章,欢迎转载,请注明出处 www.cnblogs.com/yangyaojia
[SDOI2008]沙拉公主的困惑 线性筛 素数+欧拉
题目大意
给定n,m,求在1到n!内与m!互质的个数,答案要对r取模。
输入格式:
第一行为两个整数T,R。R<=10^9+~~10,T<=10000,表示该组中测试数据数目,R为模 后面T行,每行一对整数n,m,见题目描述 m<=n
输出格式:
共T行,对于每一对N,M,输出1至N!中与M!素质的数的数量对R取模后的值
输入输出样例
input
1 11
4 2
output
1
解题分析
首先,我们来引出一个定理
如果a与b互质,那么\(b*k+a\)也与b互质。证明和证明gcd的证明类似。
反过来,我们也可以用\(gcd\)证明,
因为\(gcd(a,b)=1\),所以\(gcd(a\%b,b)=1\)
因为\(a\%b=a-k*b\),故\(gcd(a-k*b,b)=1\),及\(a-k*b\)与\(b\)互质。
根据这个特性,并且\(n>=m\),所以可以将n!分成若干段,每段为m!,每一段中与m!互质的个数都是相等的且等于1到m!中与m!互质的个数
我们可以得到式子
\(ans={\frac{n!}{m!}*\phi(m!)}\)
进一步拆开,我们可以得到 (假设p为m!的质因数,很容易可以知道,p就是所有小于m的素数,r为质因数个数)
\(ans={\frac{n!}{m!}*m!*\frac{\prod \limits_{i=1}^{r}(p_i-1)}{\prod\limits_{i=1}^{r}p_i } \to ans=n!*\frac{\prod \limits_{i=1}^{r}(p_i-1)}{\prod\limits_{i=1}^{r}p_i } }\)
因为\(ans\) 要\(\mod R\),所以我们也要算1到m的逆元,在累乘$\prod\limits_{i=1}^{r}p_i \(,乘的是\)p_i \(的逆元。
有多组询问,我们得先预处理一些数据,累乘的时候要%R
我们令\)k[i] = i! ,inv[i]为i的逆元,\(f1[i]= {\prod\limits_{a=1}^{i}(p_a-1)}\)
$ ,f2[i]={\prod\limits_{a=1}^{i}p_a} \(
\)ans=f1[m]f2[m]k[n]$
先预处理O()答案,对于询问O(1)出解
#include <cstdio>
#include <iostream>
#include <math.h>
using namespace std;
const int MAXN=10000000+10;
bool su[MAXN];
int q[MAXN][2],maxm,maxn,t,inv[MAXN],p,n,m;
int k[MAXN],f1[MAXN],f2[MAXN],ans=0;
void work()
{
inv[1]=1;k[1]=1;f1[1]=1;f2[1]=1;
for(int i=2;i<=sqrt(maxm);i++) if(!su[i])
for(int j=2;j<=maxm/i;j++) su[i*j]=1;
for(int i=2;i<=maxn;i++)
{
if(i<=maxm)
{
inv[i]=(1LL*-(p/i)*inv[p%i])%p;
inv[i]=(inv[i]%p+p)%p;
}
if(i<=maxm)
{
if(!su[i])
{
f1[i]=(1LL*f1[i-1]*((i-1)%p))%p;
f2[i]=(1LL*f2[i-1]*(inv[i]%p))%p;
}else
{
f1[i]=f1[i-1];
f2[i]=f2[i-1];
}
}
k[i]=(1LL*k[i-1]*(i%p))%p;
}
}
int main()
{
scanf("%d%d",&t,&p);
for(int i=1;i<=t;i++)
{
scanf("%d%d",&q[i][0],&q[i][1]);
maxn=max(maxn,q[i][0]);
maxm=max(maxm,q[i][1]);
}
work();
for(int i=1;i<=t;i++)
{
ans=((1LL*k[q[i][0]]%p)*1LL*(f1[q[i][1]]%p))%p;
ans=(ans*1LL*(f2[q[i][1]]%p))%p;
printf("%d\n",ans);
}
return 0;
}
/*
2 11
6 3
10 5
*/
最新文章
- 通过javascript在网页端生成zip压缩包并下载
- topcoder SRM 618 DIV2 WritingWords
- 【wikioi】1108 方块游戏(模拟)
- 类(class)、构造函数(constructor)、原型(prototype)
- bnuoj 20832 Calculating Yuan Fen(暴力模拟)
- RMAN连接及简单操作
- 就这样CSDN账号被人盗了??
- 此 ObjectContext 实例已释放,不可再用于需要连接的操作
- java--银行业务调度系统
- Teamviewer远程ssh命令行更改密码启动
- 解决git反复输入密码的问题
- wsgi 协议
- 【English】20190307
- Net-Snmp工具(学习SNMP的工具,开源项目)简单使用
- String全面解析
- 锁、C#中Monitor和Lock以及区别
- linux文件系统问题:wrong fs type, bad option, bad superblock
- SVN详细配置与使用 ——一步步教会您使用
- Web Sessions Installation
- C语言 &#183; 十六进制转八进制
热门文章
- C++对象内存布局 (一)
- Androlid入门之文件系统操作(三)文件读写
- Karma和Jasmine自动化单元测试——本质上还是在要开一个浏览器来做测试
- Cosine Similarity of Two Vectors
- Gym - 101208J 2013 ACM-ICPC World Finals J.Pollution Solution 圆与多边形面积交
- gdb打印vector
- .net中的WebForm引人MVC的控制器
- Asp.net MVC4 Step by Step (3)-数据验证
- Combotree--别样的构建层级json字符串
- 前端HTML5思维导图笔记