题目链接：
codeforces 402D
题目大意：
给出一个数列，可以进行一种操作将某一个前缀除去他们的gcd,有一个函数f(x)，f(1) = 0 , f(x) = f(x/p)+1,f(x) = f(x/p)-1(p是坏素数)问
的最大值
题目分析：首先根据那个递推式我们知道结果就是每个数的f(x)就是它的质因数当中的好素数的个数减去坏素数的个数。然后我们知道如果某个gcd中好素数的个数小于坏素数的个数，那么我们把它除掉一定可以得到更好的结果，那么如果从最后一个数开始的话，后面的数除gcd不会影响前面的数，，因为如果这部分质因数中坏素数的数量多于好素数，前面的数也一定要除掉的。所以我们贪心的倒序的做就好了。 AC代码：;int n,m,a[MAX],b[MAX];int prime[M],g[MAX];map<int,bool> mp;void init ( ){memset ( prime , 0 , sizeof ( prime ) );prime[1] = prime[0] = 1;for ( int i = 2 ; i*i < M ; i++ ){if ( prime[i] ) continue;for ( int j = i*i ; j < M ; j+= i )prime[j] = 1;}}int gcd ( int a , int b ){return b?gcd(b,a%b):a;}int main ( ){init ();while ( ~scanf ( “%d%d” , &n , &m ) ){mp.clear();for ( int i = 0 ; i < n ; i++ )scanf ( “%d” , &a[i] );for ( int i = 0 ; i < m ; i++ )scanf ( “%d” , &b[i] );g[0] = a[0];for ( int i = 0 ; i < m ; i++ )mp[b[i]] = true;for ( int i = n-1 ; i >= 0 ; i– ){int x = 0;for ( int j = 0 ; j <= i ;j++ )x = gcd ( x , a[j] );int xx = x;int num1,num2;num1 = num2 = 0;for ( int j = 2 ; j*j <= x ; j++ ){if ( prime[j] ) continue;if ( x%j ) continue;bool flag = mp[j];while ( x%j == 0 ){x/= j;if ( flag ) num1++;else num2++;}}if ( x > 1 ){if ( mp[x] ) num1++;else num2++;}if ( num1 > num2 )for ( int j = 0 ; j <= i ; j++ )a[j] /= xx;}int ans = 0;for ( int i = 0 ; i < n ; i++ ){int x = a[i];for ( int j = 2 ; j*j <= x ; j++ ){if ( prime[j] ) continue;if ( x%j ) continue;bool flag = mp[j];while ( x%j == 0 ){x /= j;if ( flag ) ans–;else ans++;}}if ( x > 1 ){if ( mp[x] ) ans–;else ans++;}}printf ( “%d\n” , ans );}}
使你疲倦的不是前面的高山，而是你鞋里的一粒沙子。
