【做题记录】HZOJ 多校-数论

B. [POI2011] SEJ-Strongbox

2025noip模拟赛73 B

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2.5e5+5;
int n,m,a[maxn];
vector<int> prm;
set<int> vis;
il void div(int x){for(int i=2;i<=x/i;i++){if(x%i==0){prm.pb(i);while(x%i==0){x/=i;}}}if(x>1){prm.pb(x);}
}
il void dfs(int x){if(vis.count(x)){return ;}vis.insert(x);for(int p:prm){if(x%p==0){dfs(x/p);}}
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>m>>n;for(int i=1;i<=n;i++){cin>>a[i];}int d=__gcd(a[n],m);div(d);for(int i=1;i<n;i++){dfs(__gcd(a[i],d));}int i=1;for(;i<=d/i;i++){if(d%i==0&&!vis.count(i)){cout<<m/i;return 0;}}for(i--;i;i--){if(d%i==0&&!vis.count(d/i)){cout<<m/(d/i);return 0;}}return 0;
}
}
signed main(){return asbt::main();}