无脑做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[2010];
map<int,vector<int>> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int mn=1e9;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mn=min(mn,a[i]);
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				mp[j].push_back(a[i]);
			if(a[i]/j!=j)mp[a[i]/j].push_back(a[i]);
			}
		}
	}
	int ans=0;
	for(auto i:mp)if(i.first<=mn){
		int v=i.first,now=i.second[0];
		for(int j:i.second)now=__gcd(now,j);
		if(v==now)ans++;
	}
	cout<<ans;
	return 0;
}

神秘数学题，神秘的做法。

#include<bits/stdc++.h>
using namespace std;
const int N=40000;
bool v1[N+10];int p[N+10],pr;
void init()
{
	pr=0;memset(v1,0,sizeof(v1));
	for(int i=2;i<=N;i++)
	{
		if(!v1[i])p[++pr]=i;
		for(int j=1;(j<=pr)&&(i*p[j]<=N);j++)
		{
			v1[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
map<int,int>mp;
int a[N],v[N],len,nw;
void dfs(int x,int s)
{
	if(x==len+1)
	{
		if(!mp[s])mp[s]=nw;
		else mp[s]=__gcd(mp[s],nw);
		return;
	}
	int x1=s;
	dfs(x+1,s);
	for(int i=1;i<=v[x];i++)
	{
		x1*=a[x];
		dfs(x+1,x1);
	}
}
signed main()
{
	init();
	int n;cin>>n;int mn=1e9;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;nw=x,len=0;mn=min(mn,x);
		for(int i=1;i<=pr;i++)if(x%p[i]==0)
		{
			int sum=0;
			while(x%p[i]==0)x/=p[i],sum++;
			a[++len]=p[i],v[len]=sum;
		}
		if(x!=1)a[++len]=x,v[len]=1;
		dfs(1,1);
	}
	int ans=0;
	for(auto i:mp)if(i.first<=mn&&i.first==i.second)ans++;
	cout<<ans;
	return 0;
}