codeforces 402d Upgrading Array

codeforces 402d Upgrading Array

​​ You have an array of positive integers a[1], a[2], …, a[n] and a set of bad prime numbers b1, b2, …, bm. The prime numbers that do not occur in the set b are considered good. The beauty of array a is the sum , where function f(s) is determined as follows:

f(1) = 0; Let’s assume that p is the minimum prime divisor of s. If p is a good prime, then , otherwise . You are allowed to perform an arbitrary (probably zero) number of operations to improve array a. The operation of improvement is the following sequence of actions:

Choose some number r (1 ≤ r ≤ n) and calculate the value g = GCD(a[1], a[2], …, a[r]). Apply the assignments: , , …, . What is the maximum beauty of the array you can get?

Input The first line contains two integers n and m (1 ≤ n, m ≤ 5000) showing how many numbers are in the array and how many bad prime numbers there are.

The second line contains n space-separated integers a[1], a[2], …, a[n] (1 ≤ a[i] ≤ 109) — array a. The third line contains m space-separated integers b1, b2, …, bm (2 ≤ b1 < b2 < … < bm ≤ 109) — the set of bad prime numbers.

Output Print a single integer — the answer to the problem.

Examples Input 5 2 4 20 34 10 10 2 5 Output -2 Input 4 5 2 4 8 16 3 5 7 11 17 Output 10 Note Note that the answer to the problem can be negative.

The GCD(x1, x2, …, xk) is the maximum positive integer that divides each xi.

题意:给定一串数列可以进行针对前i个除以他们gcd的操作 次数不限

使得最后坏数的数量最少

这题可以贪心来考虑我们知道gcd的前缀肯定是随着长度的递升而递降或不变

那么也就是说我从后面做，删除的数前面一定也找得到

那么我首先先预处理个前缀和 是所有gcd的前缀和

然后我去检验这个这个数中是好数多还是坏数多，坏数多我们就除掉它，好数多就保留他

相当于是给gcd质因数分解了一下 查找他是不是坏数可以用二分

注意如果这个数不是质数也不是他的因数要跳过x

#include#include#define M 110000#define N 5500using namespace std;inline char gc(){ static char *S,*T,now[1<<16]; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (S==T) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x; }int n,m,prime[M],not_prime[M],a[N],b[N],g[N],ans;inline int gcd(int x,int y){if (y==0) return x;return gcd(y,x%y);}int main(){ //freopen("cf.in","r",stdin); n=read();m=read();int top=0; for (int i=2;i<=M-1;++i){ if (!not_prime[i])prime[++top]=i; for (int j=1;prime[j]*i<=M;++j){ not_prime[prime[j]*i]=true; if (i%prime[j]==0) break; } } for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i<=m;++i) b[i]=read();sort(b+1,b+m+1);g[1]=a[1]; for (int i=2;i<=n;++i) g[i]=gcd(a[i],g[i-1]); //for (int i=1;i<=n;++i) printf("%d,g[i]); for (int i=n;i>=1;--i){ int exist=0,not_exist=0,gg=g[i],g1=gg; for (int j=2;j*j<=gg;++j){ if (not_prime[j]) continue;if (gg%j) continue; int pos=lower_bound(b+1,b+m+1,j)-b; while (gg%j==0){ gg/=j;if (b[pos]==j) exist++;else not_exist++; } } if (gg>1) { int pos=lower_bound(b+1,b+m+1,gg)-b; if (b[pos]==gg) exist++;else not_exist++; } if (exist>=not_exist){ for (int j=1;j<=i;++j) g[j]/=g1,a[j]/=g1; } } for (int i=1;i<=n;++i){ int x=a[i]; for (int j=2;j*j<=x;++j){ if (not_prime[j]) continue;if (x%j) continue; int pos=lower_bound(b+1,b+m+1,j)-b; while (x%j==0){ x/=j;if (b[pos]==j) ans--;else ans++; } } if (x>1) { int pos=lower_bound(b+1,b+m+1,x)-b; if (b[pos]==x) ans--;else ans++; } } printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。