BZOJ_2186_[Sdoi2008]沙拉公主的困惑_欧拉函数
2024-08-26 10:44:55
BZOJ_2186_[Sdoi2008]沙拉公主的困惑_欧拉函数
Description
大富翁国因为通货膨胀,以及假钞泛滥,政府决定推出一项新的政策:现有钞票编号范围为1到N的阶乘,但是,政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在,请你帮助沙拉公主解决这个问题,由于可能张数非常大,你只需计算出对R取模后的答案即可。R是一个质数。
Input
第一行为两个整数T,R。R<=10^9+10,T<=10000,表示该组中测试数据数目,R为模后面T行,每行一对整数N,M,见题目描述 m<=n
Output
共T行,对于每一对N,M,输出1至N!中与M!素质的数的数量对R取模后的值
Sample Input
1 11
4 2
4 2
Sample Output
1
数据范围:
对于100%的数据,1 < = N , M < = 10000000
如果gcd(i,n)=1,那么gcd(i+n,1)=1。
于是答案=$\varphi (m!)*(n!)/(m!)$
=$\varphi(m!)/(m!) *(n!)$
于是前面那个设为f[m],这个可以线筛出来,同时推出逆元。
f[m]其实就是m以内所有的质数(p-1)/p乘起来,预处理即可。
代码:
#include <stdio.h>
#define LL long long
int prim[5000001],n,m,t,p,env[10000001],fac[10000001],f[10000001],cnt;
bool vis[10000001];
int main()
{
scanf("%d%d",&t,&p);
env[1]=1;
fac[0]=fac[1]=1;
f[1]=1;
for(int i=2;i<=10000000;i++)
{
if(i<=p)
env[i]=(p-p/i)*1ll*env[p%i]%p;
else
env[i]=env[i-p];
if(!vis[i])
{
if(env[i]%p!=0)
f[i]=1ll*f[i-1]*env[i]%p*(i-1)%p;
else
{
f[i]=1ll*f[i-1]*(i-1)%p;
}
prim[cnt++]=i;
}
else f[i]=f[i-1];
for(int j=0;j<cnt&&i*prim[j]<=10000000;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)break;
}
if(i%p!=0)fac[i]=1ll*fac[i-1]*i%p;
else
{
int num=i;
while(num%p==0)num/=p;
fac[i]=fac[i-1]*num%p;
}
}
while(t--)
{
scanf("%d%d",&n,&m);
if(n>=p*2||(n>=p&&m<p))
{printf("0\n");continue;}
printf("%lld\n",1ll*f[m]*fac[n]%p);
}
}
最新文章
- XmlSerializer 对象的Xml序列化和反序列化
- ajax的使用:(ajaxReturn[ajax的返回方法]),(eval返回字符串);分页;第三方类(page.class.php)如何载入;自动加载函数库(functions);session如何防止跳过登录访问(构造函数说明)
- Fiddler使用AutoResponder进行本地文件和线上文件的映射
- mysql分区查询
- mysql 建表语句
- Ubuntu下自动挂载分区
- Run “mvn clean install” in Eclipse
- Oracle 动态视图4 V$SESSION_WAIT &; V$SESSION_EVENT
- 在linux的shell里访问一个URL
- 限制特定ip访问oracle
- java查询手机号码归属地
- cocos2d-x创建精灵动画
- python datetime模块strptime/strptime format常见格式命令_施罗德_新浪博客
- eclipse 终极操作技巧
- css鼠标样式cursor
- Unit 4.css的导入方式和选择器
- Python自动发送邮件提示:smtplib.SMTPServerDisconnected: please run connect() first
- JVM五大知识点
- org.springframework.beans.BeanUtils与org.apache.commons.beanutils.BeanUtils的copyProperties用法区别
- 搜索+剪枝——POJ 1011 Sticks