P3518
EAlivn
·
·
题解
分析
---
- 每个输入的数据与 $n$ 的 $\gcd$ 求出
- 如果 $a[i]$ 是密码，那么所有 $a[i]$ 与 $n$ 最大公约数的倍数也是密码；
- 如果 $a[i]$ 不是密码，那么所有a[i]与n最大公约数的倍数也都不是密码
- 那么从 $1 $到 $\sqrt{ a[k] }$ ~~这样分块就能使时间复杂度降低)~~ 寻找，最小且符合条件的就是密码。
代码
---
```C++
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const ll maxn=2000000+5; //数组开小了就不会过
ll a[maxn],num=0,ans=0;
inline ll read() {
ll k=0;
int fu=1;
char ch=getchar();
(ch=='-')?fu=-1:k=ch-'0';
while((ch=getchar())!=' '&&ch!='\n'){
k=k*10+ch-'0';
}
return fu*k; //ÌÓ
}
inline ll gcd(long long a,long long b) {
return b?gcd(b,a%b):a;
}//Ò²¿ÉÒÔÓÃ×Ô´øµÄ __gcd(item x,item b)
inline bool check(int x) {
for(ll i=1; i<num; i++) {
if(a[i]%x==0) return false;
}
return true;
}
int main() {
ll n=read(),k=read();
for(ll i=1; i<=k; i++) a[i]=read();
for(ll i=1; i<=k; i++) {
a[i]=gcd(a[i],n);
// a[i]=__gcd(a[i],n);
}
sort(a+1,a+k);
for(ll i=1; i<=k; i++) if(a[i]!=a[i-1]) a[++num]=a[i];
ll sak=sqrt(a[k]);
for(ll i=1; i<=sak; i++) {
if(a[k]%i==0) {
if(check(i)==true) {
ans=n/i;
break;
} else if(check(a[k]/i)==true) ans=n/a[k]*i;
}
}
printf("%lld\n",ans);
return 0;
}
```
```C++
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const ll maxn=2000000+5;
ll a[maxn],num=0,ans=0;
inline ll read() {
ll k=0;
int fu=1;
char ch=getchar();
(ch=='-')?fu=-1:k=ch-'0';
while((ch=getchar())!=' '&&ch!='\n'){
k=k*10+ch-'0';
}
return fu*k; //ÌÓ
}
inline ll gcd(long long a,long long b) {
return b?gcd(b,a%b):a;
}//Ò²¿ÉÒÔÓÃ×Ô´øµÄ __gcd(item x,item b)
inline bool check(int x) {
for(ll i=1; i<num; i++) {
if(a[i]%x==0) return false;
}
return true;
}
int main() {
ll n=read(),k=read();
for(ll i=1; i<=k; i++) a[i]=read();
for(ll i=1; i<=k; i++) {
a[i]=gcd(a[i],n);
// a[i]=__gcd(a[i],n);
}
sort(a+1,a+k);
for(ll i=1; i<=k; i++) if(a[i]!=a[i-1]) a[++num]=a[i];
ll sak=sqrt(a[k]);
for(ll i=1; i<=sak; i++) {
if(a[k]%i==0) {
if(check(i)==true) {
ans=n/i;
break;
} else if(check(a[k]/i)==true) ans=n/a[k]*i;
}
}
printf("%lld\n",ans);
return 0;
}
```