问题 E: 好朋友

时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
众所周知，XZ&CHR是好朋友……
这天，CHR打算考验一下XZ与自己的默契度，他想了n个正整数:a₁ ~ a_n，为了不为难XZ，CHR只要求说出一个数，这个数是a₁ ~ a_n中任何一个数的倍数即可。当然，这还是十分困难，XZ知道后，觉得这很难，就来问问你：如果他在1~m中随机说出一个数，通过考验的概率是多少？

输入
第一行输入一个正整数T，代表有T组数据。
对于每一组数据，第一行输入n，m, 第二行输入a1~an，含义见题目描述。

输出
为防止有精度问题，对于每一组数据输出概率乘上m，即一个正整数代表答案。
样例输入 Copy
1
2 10
2 3
样例输出 Copy
7
提示
样例解释：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。

思路：大致是BFS+容斥定理

具体来说：首先我们的目的是找到各个数的倍数要求是不重不漏在1-m之内，然后我们要知道，如果a=kb（k>=1），则a的所有倍数一定也是b的倍数所以a的倍数就可以不用考虑了，一个数的倍数在1-m范围内有m整除这个数，这个应该很好理解。当然我们可以想到，如果把a1和a2的倍数提出来的话一定有重的，就是<mark>a1和a2的最小公倍数的倍数</mark>这个地方一定是最小公倍数，（不是乘积！不是乘积！不是乘积！！！，只能说不一定嘻嘻）这样我们可以联想到容斥定理，<mark>奇数个的最小公倍数的倍数个数加上，偶数的最小公倍数的倍数的个数减去</mark>，（有点绕，多看两遍应该能懂），之后就是如何实现奇数个或者偶数个的最小公倍数形成，dfs：推出条件就是1，最小公倍数大于m退出，2，当搜到最后一个数时退出来（这里是去除重复加上或者减去，就好比 23和3*2，从2搜到3，然后你回到从3开始搜如果再搜一次2的话很明显重了），然后用一个数标记个数，奇数+，偶数-；

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
 
inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
map<ll,ll> mp;
ll gcd(ll a,ll b){
    while(b){
        ll t=a%b;
        a=b;b=t;
    }
    return a;
}
ll a[20],n,m,sum;
ll dis[20];
void dfs(ll x,ll ans,ll p){
    if(ans>m) return;
    if(x!=0){
    if(x%2==1) sum+=m/ans;
    else sum-=m/ans;
  // cout<<sum<<endl;
    }
    if(p==n) return;
     
    for(int i=p+1;i<=n;i++)
    {
        if(dis[i]==0){
            dis[i]=1;//应该不是很必要了 因为 用到了 p==n这个退出条件
            dfs(x+1,ans/gcd(a[i],ans)*a[i],i);
            dis[i]=0;
        }
    }
}
 
int main(){
    ll t;
    cin>>t;
    while(t--){
        cin>>n>>m;
         
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        sum=0;
        for(int i=1;i<=n;i++){
            ll flag=0;
            for(int j=1;j<i;j++)
                if(a[i]%a[j]==0){
                    flag=j;
                    break;
                }
            if(flag!=0) {
                a[i]=m+1;
            }
        }
         
        dfs(0,1,0);
         cout<<sum<<endl;   
    }
    return 0;
}

好朋友（bfs）

问题 E: 好朋友