UVA 4683 - Find The Number - c++编程基础

这题的意思是给一个集合，最多有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 
  
   
#include 
   
     #include 
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 //#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<
                
                 = n) high = mid-1; else low = mid+1; } printf("%I64d\n",low); } return 0; }