JZOJ 1241. Number

2024-04-03 09:17:48

题目

Description

有N(2<=N<=15)个数A1,A2,....,An-1,An,如果在这N个数中，有且仅有一个数能整除m，那么整数m就是一个幸运数，你的任务就是在给定A1,A2,....,An-1,An的情况下，求出第k小的幸运数。

Input

第一行为一整数数N,K(2<=N<=15,1<=K<=2^31-1)，意义如上述。
接下来一行有N个整数，A1,A2,....,An-1,An,这N个整数均不超过2^31-1。

Output

输出一行，仅包含一个整数ans，表示第K小的幸运数。答案保证不超过10^15。

Sample Input

Sample Output

输出1：
8

输出2：
12500

Data Constraint

Hint

对于50%的数据，N<=5,ANS<=100000
对于80%的数据，N<=10,ANS<=10^15
对于100%的数据，N<=15,ANS<=10^15

分析

考场只会打暴力（50）
然后原来是个二分
枚举mid前有k个满足的数
我们可以求出输入的数的lcm
然后容斥就好啊

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #define ll long long
 4 using namespace std;
 5 int a[20];
 6 int b[20];
 7 int n,k;
 8 struct sb
 9 {
10     ll v,num;
11 }l[100001];
12 int cnt=0;
13 bool cmp(sb a,sb b)
14 {
15     if (a.num<b.num) return true;
16     return false;
17 }
18 ll gcd(ll a,ll b){
19     if(a%b==0)  return b;
20     else return gcd(b,a%b);
21 }
22 ll lcm(ll a,ll b){
23     return a*b/gcd(a,b);
24 }
25 void dfs(int f,int gs)
26 {
27     if (gs>n) return;
28     long long p=1;
29     for (int i=1;i<=gs;i++)
30     {
31         p=lcm(p,b[i]);
32         if (p>1000000000000000) return;
33     }
34     l[++cnt].num=gs; l[cnt].v=p;
35     for (int i=f+1;i<=n;i++)
36     {
37         b[gs+1]=a[i];
38         dfs(i,gs+1);
39     }
40 }
41 int main ()
42 {
43     cin>>n>>k;
44     for (int i=1;i<=n;i++)
45         cin>>a[i];
46     for (int i=1;i<=n;i++)
47     {
48         b[1]=a[i];
49         dfs(i,1);
50     }
51     sort(l+1,l+1+cnt,cmp);
52     ll lll=1,r=1e15,mid;
53     while (lll<=r)
54     {
55         mid=lll+r>>1;
56         ll kk=0;
57         for (int i=1;i<=cnt;i++)
58             if (l[i].num%2==1) kk+=mid/l[i].v*l[i].num;
59             else kk-=mid/l[i].v*l[i].num;
60         if (kk<k) lll=mid+1;
61         else r=mid-1;
62     }
63     cout<<lll;
64 }

码农公寓

题目