uva 10325 The Lottery(组合数学-容斥原理)

 The Lottery 

The Sports Association of Bangladesh is in great problem with their latest lottery ‘Jodi laiga Jai‘. There are so many participants this time that they cannot manage all the numbers. In an urgent meeting they have
decided that they will ignore some numbers. But how they will choose those unlucky numbers!! Mr. NondoDulal who is very interested about historic problems proposed a scheme to get free from this problem.

You may be interested to know how he has got this scheme. Recently he has read the Joseph‘s problem.

The Problem

There are N tickets which are numbered from 1 to N. Mr. Nondo will choose M random numbers and then he will select those numbers which is divisible by at least one of those M numbers. The numbers which are not
divisible by any of those M numbers will be considered for the lottery.

As you know each number is divisible by 1. So Mr. Nondo will never select 1 as one of those M numbers. Now given N,M and M random numbers, you have to find out the number of tickets which will be considered for
the lottery.

The Input

Each input set starts with two Integers N (10<=N<2^31) and M (1<=M<=15). The next line will contain M positive integers each of which is not greater than N. Input is terminated by EOF.

The Output

Just print in a line out of N tickets how many will be considered for the lottery.

Sample Input

10 2
2 3
20 2
2 4

Sample Output

3
10

Md. Kamruzzaman

题目大意:

给定n,m个数,问你1~n中有多少个数不能被m个数任意之一整数?

解题思路:

利用容斥原理,这篇已写过:http://blog.csdn.net/a1061747415/article/details/38272371

解题代码:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
int n,m,a[20];

ll gcd(ll a,ll b){
    return b>0 ? gcd(b,a%b):a;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        int ans=0;
        vector <int> v;
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
            if(a[i]>0) v.push_back(a[i]);
        }
        m=v.size();
        for(int i=1;i<(1<<m);i++){
            int cnt=0;
            ll x=1;
            for(int t=0;t<m;t++){
                if(i&(1<<t)){
                    cnt++;
                    x=x*v[t]/gcd(x,v[t]);
                }
            }
            if( cnt&1 ) ans+=(n)/x;
            else ans-=(n)/x;
        }
        cout<<n-ans<<endl;
    }
    return 0;
}
时间: 08-23

uva 10325 The Lottery(组合数学-容斥原理)的相关文章

UVA 10883 - Supermean(组合数学+数值优化)

题目链接:10883 - Supermean 题意:求超级平均数,就是相邻两个算一个平均数,直到剩下一个数,求数值. 思路:画图很容易推断出公式.就拿最后一组样例来说 1     2      3      4      5 1.5  2.5   3.5   4.5 2       3      4 2.5   3.5 3 观察可以发现都是从顶到底,看又几条路线,就有几次,然后最后每个数字在除上相应次数的2,那几条路线就是C(n - 1, [0 - n - 1])的组合数. 所以ans = su

UVA 11806 - Cheerleaders(数论+容斥原理)

题目链接:11806 - Cheerleaders 题意:在一个棋盘上,要求四周的四行必须有旗子,问有几种摆法. 思路:直接算很容易乱掉,利用容斥原理,可知AUBUCUD = |A| + |B| + |C| + |D| - |AB| - |BC| - |AC| - |AD| - |BD| - |CD| + |ABC| + |ABD| + |ACD| + |BCD| - |ABCD| 由此利用位运算去计算即可 代码: #include <stdio.h> #include <string.

UVA 11014 - Make a Crystal(容斥原理)

UVA 11014 - Make a Crystal 题目链接 题意:给定一个NxNxN的正方体,求出最多能选几个整数点.使得随意两点PQ不会使PQO共线. 思路:利用容斥原理,设f(k)为点(x, y, z)三点都为k的倍数的点的个数(要扣掉一个原点O).那么全部点就是f(1),之后要去除掉共线的,就是扣掉f(2), f(3), f(5)..f(n).n为素数.由于这些素数中包括了合数的情况,而且这些点必定与f(1)除去这些点以外的点共线,所以扣掉.可是扣掉后会扣掉一些反复的.比方f(6)在f

UESTC - 1544 当咸鱼也要按照基本法 组合数学 容斥原理

http://acm.uestc.edu.cn/#/problem/show/1544 考虑一下2.2.2这样的情况.答案应该是n / 2 如果只选一个的情况下,对答案的贡献是正的,但是这里有三个,也就是我们统计了3 * n / 2,统计多了. 那么对于任选两个数的情况,有三种,(2, 2) * 3,分别都是不同位置的2, /**************************************/ 我做的时候是发现,先讨论只有 2.2的情况,也就是只有两个数的时候,ans = 0,这个时候

容斥原理

对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率. 描述 容斥原理可以描述如下: 要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分. 关于集合的原理公式 上述描述的公式形式可以表示如下:                  它可以写得更简洁一些,我们将B作为所有Ai的集合,那么容斥原理就变成了: 这个

【转载】【容斥原理】

转载自 http://www.cppblog.com/vici/archive/2011/09/05/155103.html 容斥原理(翻译) 前言: 这篇文章发表于http://e-maxx.ru/algo/inclusion_exclusion_principle,原文是俄语的.由于文章确实很实用,而且鉴于国内俄文资料翻译的匮乏,我下决心将其翻译之.由于俄语对我来说如同乱码,而用Google直接翻译中文的话又变得面目全非,所以只能先用Google翻译成英语,再反复读,慢慢理解英语的意思,实在

容斥原理 (转载)

前言: 这篇文章发表于http://e-maxx.ru/algo/inclusion_exclusion_principle,原文是俄语的.由于文章确实很实用,而且鉴于国内俄文资料翻译的匮乏,我下决心将其翻译之.由于俄语对我来说如同乱码,而用Google直接翻译中文的话又变得面目全非,所以只能先用Google翻译成英语,再反复读,慢慢理解英语的意思,实在是弄得我头昏脑胀.因此在理解文章意思然后翻译成中文的时候,中文都不知道如何表述了.而又由于我对容斥原理知识的匮乏,很可能有些地方我的表述是错误的

O(N)的素数筛选法和欧拉函数

首先,在谈到素数筛选法时,先涉及几个小知识点. 1.一个数是否为质数的判定. 质数,只有1和其本身才是其约数,所以我们判定一个数是否为质数,只需要判定2~(N - 1)中是否存在其约数即可,此种方法的时间复杂度为O(N),随着N的增加,效率依然很慢.这里有个O()的方法:对于一个合数,其必用一个约数(除1外)小于等于其平方根(可用反证法证明),所以我们只需要判断2-之间的数即可. bool is_prime(int num) { const int border = sqrt(num); for

Topcoder SRM 144 DIV 1

BinaryCode 模拟 题意是:定义串P,Q,其中Q[i]=P[i-1]+P[i]+P[i+1],边界取0,并且P必须是01串.现在给你Q,让你求出P. 做法是:枚举第一位是1还是0,然后就可以推到出P[i]=Q[i-1]-P[i-1]-P[i-2],需要注意一下边界就好. Lottery 组合数学 题意是:给你四种买彩票,将他们的中奖概率排序,这四种彩票都是从1到a中取b个数字,第一种是随便取,第二种是选取的必须是有序的,第三种是选取的必须是不同的,第四种是选取的必须是有序且不同的. 做法