题目链接：http://www.ifrog.cc/acm/problem/1138

题解：这题就是简单的容斥，但是和标准的不太一样，这个是只加上出现奇数的。其实也是挺简单的。

容斥原式：     

只求奇数那么就要球容斥的系数如果n=2,显然为a+b-2*a*b,n=3,a+b+c-2*a*b-2*a*c-2*b*c+4*a*b*c,n=4.....不妨设f(x)表示由x个数组合出来的数系数为多少，那么当x为奇数时f(x)=1-(f(1)*n-f(2)*n+f(3)*n-........-f(x-1)*n),当x为偶数的时候f(x)=-(f(1)*n-f(2)*n+f(3)*n-f(4)*n+.....+f(x-1)*n)这个规律是总结出来的具体画一下图。然后可以得到系数为2^(k - 1),

#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std;typedef long long ll;ll gcd(ll a , ll b) {    return (b > 0) ? gcd(b , a % b) : a;}int arr[20];int main() {    int t;    scanf("%d" , &t);    while(t--) {        int n , m;        ll ans = 0;        scanf("%d%d" , &n , &m);        for(int i = 0 ; i < m ; i++) scanf("%d" , &arr[i]);        for(int i = 1 ; i < (1 << m) ; i++) {            ll num = 0;            ll lcm = 1;            for(int j = 0 ; j < m ; j++) {                if(i & (1 << j)) {                    num++;                    lcm = lcm/gcd(lcm , (ll)arr[j]) * (ll)arr[j];                    if(lcm > n) break;                }            }            if(num % 2) ans += n / lcm * (1 << (num - 1));            else ans -= n / lcm * (1 << (num - 1));        }        printf("%lld\n" , ans);    }    return 0;}

玲珑杯 1138 - 震惊，99%+的中国人都会算错的问题（容斥）