好朋友容斥原理-白红宇的个人博客

好朋友容斥原理

发布日期：2021-09-25 23:57:40 浏览次数：11 分类：技术文章

本文共 1245 字，大约阅读时间需要 4 分钟。

好朋友

时间限制: 1 Sec 内存限制: 128 MB

题目描述

众所周知，XZ&CHR是好朋友……

这天，CHR打算考验一下XZ与自己的默契度，他想了n个正整数:a1~an，为了不为难XZ，CHR只要求说出一个数，这个数是a1 ~ an中任何一个数的倍数即可。当然，这还是十分困难，XZ知道后，觉得这很难，就来问问你：如果他在1~m中随机说出一个数，通过考验的概率是多少？

输入

第一行输入一个正整数T，代表有T组数据。

对于每一组数据，第一行输入n，m, 第二行输入a1~an，含义见题目描述。

输出

为防止有精度问题，对于每一组数据输出概率乘上m，即一个正整数代表答案。

样例输入 Copy

2 10

2 3

样例输出 Copy

提示

样例解释：2、4、6、8、10是2的倍数，其他数中3、9是3的倍数，共7个。

【数据范围】

对于30%的数据，m ≤ 1000。

对于另外20%的数据，n = 1。

对于另外20%的数据，n = 2。

对于所有数据，n ≤ 10，1＜ai ≤ m ≤ 10^9，T ≤ 10000。

题目很明显就是容斥原理，直接dfs枚举他们组合的方案数就行了，循环实现可能有点毛病。~~再也不写循环了~~

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int t;int n;LL a[N],m,ans; LL gcd(LL a,LL b){ return b? gcd(b,a%b):a; }LL lcm(LL a,LL b){ return a/gcd(a,b)*b;}void dfs(int u,int f,LL t){ if(u!=1) ans+=m/t*f; for(int i=u;i<=n;i++) dfs(i+1,f*-1,lcm(t,a[i]));}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>t; while(t--) { scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); ans=0; dfs(1,-1,1); printf("%lld\n",ans); } return 0;}

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105902237 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：upc 单词表字典树 + dfs

下一篇：斐波那契数列线性dp

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章