思路：对于每个数分解质因子然后记录每一个质因子的个数，对与在b中出现的质因子就减去1，否则加1，求出总的，然后从后面一次对它们的最大公约数，然后判断除以最大公约数之后，改变量是不是变化，求最大值，变化量为负值的话减去。
1 #include <cstdio> 2 #include <cstring> 3 #include <map> 4 #include <set> 5 #include <algorithm> 6 using namespace std; 7 8 set<int>q; 9 int n,m; 10 int a[50010],b[50010]; 11 int g[50010]; 12 13 int gcd(int a,int b) 14 { 15 return b==0?a:gcd(b,a%b); 16 } 17 18 int Get_num(int x) 19 { 20 int ans=0; 21 map<int,int>p; 22 for(int j=2; j*j<=x; j++) 23 { 24 if(x%j==0) 25 { 26 while(x%j==0) 27 { 28 p[j]++; 29 x/=j; 30 } 31 } 32 } 33 if(x>1) p[x]++; 34 map<int,int>::iterator it; 35 for(it=p.begin(); it!=p.end(); it++) 36 { 37 if(q.find(it->first)==q.end()) ans+=it->second; 38 else ans-=it->second; 39 } 40 return ans; 41 } 42 43 int main() 44 { 45 46 scanf("%d%d",&n,&m); 47 for(int i=1; i<=n; i++) 48 { 49 scanf("%d",&a[i]); 50 } 51 for(int j=1; j<=m; j++) 52 { 53 scanf("%d",&b[j]); 54 q.insert(b[j]); 55 } 56 int ans=0; 57 for(int i=1; i<=n; i++) 58 { 59 ans+=Get_num(a[i]); 60 } 61 for(int i=1; i<=n; i++) 62 { 63 if(i==1) g[i]=a[i]; 64 else g[i]=__gcd(g[i-1],a[i]); 65 } 66 int c=1; 67 for(int i=n; i>=1; i--) 68 { 69 int h=g[i]/c; 70 int s=Get_num(h); 71 if(s<0) 72 { 73 ans-=s*i; 74 c*=h; 75 } 76 } 77 printf("%d ",ans); 78 return 0; 79 }