洛谷 P3518 [POI2011] SEJ-Strongbox 题解

思路：

首先先将每个输入的数据与n的最大公约数求出（因为如果a[i]是密码，那么所有a[i]与n最大公约数的倍数也是密码；于是如果a[i]不是密码，那么所有a[i]与n最大公约数的倍数也都不是密码）再从1到sqrt(a[k])(其实1到a[k]也行)找，最小且符合条件就是最小密码。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef unsigned long long ull;
 8 typedef long long ll;
 9 ll n,k;
10 ll a[250005];
11 ll num=0;
12 ull ans;inline ll read()
13 {
14     ll x=0;
15     bool f=1;
16     char c=getchar();
17     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
18     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
19     if(f) return x;
20     return 0-x;
21 }
22 inline ll gcd(long long a,long long b)//求两个数最大公约数的函数 
23 {
24     return b?gcd(b,a%b):a;
25 }
26 inline bool check(int x)
27 {
28     for(ll i=1;i<=num-1;i++)//-1：不包含密码与n的最大公约数 
29     {
30         if(a[i]%x==0)
31         {
32             return false;
33         }
34     }
35     return true;
36 }
37 int main()
38 {
39     n=read();k=read();
40     for(ll i=1;i<=k;i++)
41     {
42         a[i]=read();
43     }
44     for(ll i=1;i<=k;i++)
45     {
46         a[i]=gcd(a[i],n);//求a[i]与n的最大公约数 
47     }
48     sort(a+1,a+k);//排序（不排也可以，只不过时间更长）至于不是 sort(a+1,a+k+1)是因为密码不能与不是密码的数混在一起 
49     for(ll i=1;i<=k;i++)
50     {
51         if(a[i]!=a[i-1])//去重 
52         {
53             num++;
54             a[num]=a[i];
55         }
56     }
57     for(ll i=1;i<=sqrt(a[k]);i++)//节约时间 
58     {
59         if(a[k]%i==0)//第一层筛选 
60         {
61             if(check(i)==true)//既是最小又是符合题意的 ，一定是最优解 
62             {
63                 ans=n/i;
64                 break;
65             }
66             else if(check(a[k]/i)==true)//符合条件但不一定是最小，算但不break 
67             {
68                 ans=n/a[k]*i;
69             }
70         }
71     }
72     cout<<ans;
73     return 0;
74 }

请各位大佬斧正（反正我不认识斧正是什么意思）