容斥原理 求M以内有多少个跟N是互质的
2024-09-30 10:23:14
开始系统的学习容斥原理!通常我们求1~n中与n互质的数的个数都是用欧拉函数!
但如果n比较大或者是求1~m中与n互质的数的个数等等问题,要想时间效率高的话还是用容斥原理!
本题是求[a,b]中与n互质的数的个数,可以转换成求[1,b]中与n互质的数个数减去[1,a-1]与n互质的数的个数。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define LL long long #define maxn 70 LL prime[maxn]; LL make_ans(LL num,int m) { LL ans=,tmp,i,j,flag; ;i<(LL)(<<m);i++) //用二进制来1,0来表示第几个素因子是否被用到,如m=3,三个因子是2,3,5,则i=3时二进制是011,表示第2、3个因子被用到 { tmp=,flag=; ;j<m;j++) <<j)))//判断第几个因子目前被用到 flag++,tmp*=prime[j]; )//容斥原理,奇加偶减 ans+=num/tmp; else ans-=num/tmp; } return ans; } int main() { ,m; LL n,a,b,i; scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d",&a,&b,&n); m=; ;i*i<=n;i++) //对n进行素因子分解 ) { prime[m++]=i; ) n/=i; } ) prime[m++]=n; printf(-make_ans(a-,m))); } ; }
最新文章
- 面试题整理:SQL(二)
- 常用RSS订阅地址
- php : 匿名函数(闭包) [一]
- How to configure Veritas NetBackup (tm) to write Unified and Legacy log files to a different directory
- P1391 走廊泼水节
- SQL Server 非聚集索引的覆盖,连接,交叉和过滤 <;第二篇>;
- [jquery]基础篇--this与$this区别
- Apache配置虚拟主机后,不能访问localhost
- hdu 2296 aC自动机+dp(得到价值最大的字符串)
- arcEngine开发之activeView.PartialRefresh(译)
- ajax错误类型大全
- 在.net core web项目中生成二维码
- robot framework关键词记录单(更新中)
- vue-all
- GCD与LCM
- MFC 运行报错:Debug Assertion Failed! dbgheap.c
- centos安装jdk1.8
- MATLAB 求两个矩阵的 欧氏距离
- Kettle定时抽取两个库中的两个表到目标库SYS_OPLOG表
- Scala语言学习笔记(4)