uva 4683

这题的意思是给一个集合，最多有12个元素。

找出仅仅能被集合中一个仅且一个数整除的第n个数。

(n <= 10^15)。

我用容斥原理做的。先把能被每一个数整除的元素个数累加，当然会有反复的。若某个数由集合中两个数组成，那么要减去全部这个数的整数倍，并且要减两次，由于他是两个数的公约数，而当某个数是当中三个数的公约数，那他一定也是两个数的公约数，这样就多减了c[k][2]个，就得加上。以此类推。

要求第n个数，题目说答案最大是10^15，我以10^15为界限进行二分。对于[1,m]内若符合条件的数是res个。若res >= n，那么high = mid-1，否则low = mid+1。

可是我的代码没过，无限TLE。。代码先贴这里。希望路过的大神给予指点。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <bitset>

#include <list>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

//#define long long __int64

//#define LL long long

#define eps 1e-9

#define PI acos(-1.0)

//typedef __int64 LL;

using namespace std;

const long long Max = 1000000000000000;

int k;

long long n;

int a[15];

long long C[15][15];

long long gcd(long long a, long long b)

{

    if(b == 0) return a;

    return gcd(b,a%b);

}

long long lcm(long long a, long long b)

{

    return a/gcd(a,b)*b;

}

void init()

{

    memset(C,0,sizeof(C));

    for(int i = 1; i <= 12; i++)

    {

        for(int j = 0; j <= i; j++)

        {

            if(j == 0 || j == i)

                C[i][j] = 1;

            else if(j == 1)

                C[i][j] = i;

            else

                C[i][j] = C[i-1][j-1] + C[i-1][j];

        }

    }

}

long long cal(long long m)

{

    long long ans = 0;

    for(int i = 1; i < (1<<k); i++)

    {

        int cnt = 0;

        long long mul = 1;

        for(int j = 0; j < k; j++)

        {

            if(i&(1<<j))

            {

                cnt++;

                mul = lcm(mul,a[j]);

            }

        }

        if(cnt&1)

            ans += C[k][cnt-1]*(m/mul);

        else

            ans -= cnt*(m/mul);

    }

    return ans;

}

int main()

{

    int test;

    init();

    scanf("%d",&test);

    while(test--)

    {

        scanf("%d %I64d",&k,&n);

        for(int i = 0; i < k; i++)

        {

            scanf("%d",&a[i]);

        }

        long long low = 0,high = Max;

        while(low <= high)

        {

            long long mid = (low + high)/2;

            long long res = cal(mid);

            if(res >= n)

                high = mid-1;

            else

                low = mid+1;

        }

        printf("%I64d\n",low);

    }

    return 0;

}