容斥模闆

//判斷1-n有多少個M個因子任一個的倍數
int n,m,cnt;
ll ans ,a[30];
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

void DFS(int cur,ll lcm,int id)  
{// 目前第幾個因子  這些因子的最小共公倍數 目前總因子
    lcm = a[cur]/gcd(a[cur],lcm)*lcm;
    if(id&1)   //奇加偶減
        ans += (n-1)/lcm;
    else
        ans -= (n-1)/lcm;
    for(int i= cur+1;i<cnt;i++)
        DFS(i,lcm,id+1);
}
int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        cnt = 0;
        int x;
        while(m--)
        {
            scanf("%d",&x);
            if(x!=0)
                a[cnt++] = x;
        }
        ans = 0;
        for(int i=0;i<cnt;i++) //周遊每種組合 從1開始
            DFS(i,a[i],1);
        printf("%lld\n",ans);
    }
    return 0;
}
           

//判斷1-n 有多少個符合m^k的數
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll ans ,n;
void dfs(int cur,int s,int cnt)
{
    ll t = (ll)pow(n,1.0/s);
    if(t>1)
    {
        if(cnt&1)
            ans += t-1;
        else
            ans -= t-1;
    }
    if(cnt>2) return ;
    for(int i = cur+1;i<17;i++)
        dfs(i,s*p[i],cnt+1);
}
int main()
{
    while(scanf("%lld",&n) != EOF)
    {
        ans = 1;
        for(int i=0;i<17;i++)// 最大2^59 2^(2*3*5)
            dfs(i,p[i],1);
        cout<<ans<<endl;
    }
    return 0;
}