食人魔法师的盛宴

蓝胖的技能火焰爆轰+多重施法可以多次造成对方伤害. 这里为了简化问题, 假设该技能的施法方向在一条直线上.
技能参数由集合S={a_1,...a_m}给定, 其中m<=12, 2<=ai<=1e5, 不存在ai 整除 aj, i!=j的情况.
a_i表示距离蓝胖a_i*k(for all k>=1)的点位将受到轰击. 点位每受到一次轰击凹陷深度+1.
伊始地面是平的. 蓝胖想知道第 n（n <= 1e15） 个深度为1的点位距离它多远.

输入
多样例, 第一行是样例数, 每个样例由2行构成, 第一行给定 m 和 n
第二行给定 m 个正整数

输出
答案(保证<=1e15)

样例输入
2 
2 4 
2 3 
3 10 
6 11 20

样例输出
8 
36

hint 第一个样例, 2、3、4、8，所以8 是第四个, 注意, 6因为可以被2、3整除, 所以6不是答案

这题的意思是给一个集合S，最多有m (<=12)个两两不同的元素, 每个元素在 [2, 1e5], 而且不存在一个数能整除
另一个数的情况，找出恰能被集合中一个元素整除的第n个数。

//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <map>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define int long long
#define re register int
#define ci const int
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to, len; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ild inline double
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;
namespace fastio
{
 const int BUF = 1 << 21;
 char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
 ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
 ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
 ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
 ilv back() { pr1--; }
 ili read(int &x)
 {
  x = 0; int f = 1; char c = gc(); if (!~c) return EOF;
  while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
  while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
  x *= f; return 1;
 }
 ili read(double &x) 
 {
  int xx = 0; double f = 1.0, fraction = 1.0; char c = gc(); if (!~c) return EOF;
  while (!isdigit(c)) { if (c == '-') f = -1.0; c = gc(); }
  while (isdigit(c)) { xx = (xx << 3) + (xx << 1) + (c ^ 48), c = gc(); }
  x = xx;
  if (c ^ '.') { x = f * xx; return 1; }
  c = gc();
  while (isdigit(c)) x += (c ^ 48) * (fraction /= 10), c = gc();
  x *= f; return 1;
 }
 ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
 ilv writeln(int x) { write(x);pc(10); }
 ili read(char *x)
 {
  char c = gc(); if (!~c) return EOF;
  while(!isalpha(c) && !isdigit(c)) c = gc();
  while (isalpha(c) || isdigit(c)) *x++ = c, c = gc();
  *x = 0; return 1;
 }
 ili readln(char *x)
 {
  char c = gc(); if (!~c) return EOF;
  while(c == 10) c = gc();
  while(c >= 32 && c <= 126) *x++ = c, c = gc();
  *x = 0; return 1;
 }
 ilv write(char *x) { while(*x) pc(*x++); }
 ilv writeln(char *x) { write(x); pc(10); }
 ilv write(char c) { pc(c); }
 ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
const int maxn = 1e15;
int k, n, a[15], lcms[5005], sign[5005];

int gcd(int a, int b)
{
 return b ? gcd(b, a % b) : a;
}

ili lcm(int a, int b)
{
 return a / gcd(a, b) * b;
}

ilv init()
{
 for (re i = 1, mul, sign1; i < 1 << k; i++)
 {
  mul = 1, sign1 = 0;
  for (re j = 0; j < k; j++)
  {
   if (i & (1 << j))
   {
    mul = lcm(mul, a[j]), ++sign1;
   }
  }
  lcms[i] = mul, sign[i] = sign1;
 }
}

ili ck(int x)
{
 int ans = 0;
 for (re i = 1, t; i < 1 << k; i++)
 {
  t = x / lcms[i] * sign[i];
  ans += sign[i] & 1 ? t : -t;
 }
 return ans >= n;
}

ili kk()
{
 int lo = a[0], hi = maxn, ans = -1, mid;
 while (lo <= hi)
 {
  mid = lo + hi >> 1;
  if (ck(mid))
  {
   ans = mid;
   hi = mid - 1;
  }
  else
  {
   lo = mid + 1;
  }
 }
 return ans;
}

signed main()
{
#ifdef LOCAL
 freopen("d:\\data.in", "r", stdin);
// freopen("d:\\my.out", "w", stdout);
#endif
 int kase; read(kase);
 while (kase--)
 {
  read(k), read(n);
  for (re i = 0; i < k; i++) read(a[i]);
  sort(a, a + k);
  init();
  writeln(kk());
 }
 flush();
 return 0;
}

Accepted | C++ | 326ms