缘起
食人魔法师Aggron最近把自己的火焰爆轰技能提升到了极致. 它想知道它的轰击效果如何, 你能帮帮它吗? 本文的例题是 Uva 4683 Find the Number
分析
代码语言：javascript复制蓝胖的技能火焰爆轰 多重施法可以多次造成对方伤害. 这里为了简化问题, 假设该技能的施法方向在一条直线上.
技能参数由集合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不是答案
先简化一下扯淡的题意~
代码语言：javascript复制这题的意思是给一个集合S，最多有m (<=12)个两两不同的元素, 每个元素在 [2, 1e5], 而且不存在一个数能整除
另一个数的情况，找出恰能被集合中一个元素整除的第n个数。
因为答案具备单调性，所以自然联想到二分答案. 众所周知, 二分的核心在于check函数, 即我们将 x 固定下来，然后去计算 [1, x] 中恰能被S中的一个元素整除的数的个数w. 如果 w >=n, 则满足条件，并且我们将 x 进一步减小, 如果 < n, 则我们必须将 x 增大——请注意这里的二分逻辑！！！因为要求的答案是最小的那个 x, 如果你把二分的逻辑改成 如果 <=n, 则满足条件，并且我们将 x 进一步增大, 如果 > n, 则我们必须将 x 减小 那么求的是最大的满足条件的答案, 这就不对了.
所以本题的核心在于给定 x，如何计算 [1,x] 内恰好能被S 中的一个元素整除的数的个数.
一般性的考虑，假设有一个 [1,..,x] 中的数 y 有 k 个S中的因子, 注意到以下等式
我们记
，显然等式右边的 k 是 y 的函数，记做k = k(y), 于是我们知道
所以[1,..,x] 内恰好能被S中一个元素整除的元素的个数是
其中组合数
，而注意，如果令
的话, 则
其中lcm表示最小公倍数，除法按照 5/2=2 这样来理解。所以本题就破了，[1,x]内恰好能被S中一个数整除的元素的个数是
又注意到 |S| <=12, 比较小，所以必须联想到状压. 我们完全可以二进制枚举所有A.
代码语言：javascript复制//#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;
}
ac情况
代码语言：javascript复制Accepted | C | 326ms
