Codeforces 402 D Upgrading Array

题意：给一个坏的素数序列，不在这个素数序列里面的都是好素数，然后再给你一个序列，序列可以得到一个Fvalue

定义是这样的 f函数的定义又是这样的。。

可以进行无数次以下操作

最后问你能得到的最大的 Fvalue 是多少。

解题思路：先把前n项的 gcd 值预处理，然后再从后往前dp，看是否要选择现在的gcd作为前面的gcd就行了。

解题代码：

  1 // File Name: 402d.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年03月29日 星期日 16时42分46秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 32105
 26 using namespace std;
 27 int n , m; 
 28 int a[maxn];
 29 int b[maxn];
 30 int prime[maxn];
 31 int hs[maxn];
 32 set<int> mp;
 33 int tt; 
 34 void sai()
 35 {
 36     for(int i = 2;i < maxn ;i ++)
 37     {
 38         int k = i * i ; 
 39         while(k < maxn)
 40         {
 41           hs[k] = 1; 
 42           k += i ; 
 43         }
 44     }
 45     
 46     for(int i = 2;i < maxn ;i ++)
 47     {
 48        if(hs[i] == 0 )
 49        {
 50           tt ++ ; 
 51           prime[tt] = i ; 
 52        }
 53     }
 54     //printf("%d
",tt);
 55 }
 56 int cv ;
 57 int solve(int k ,int status)
 58 {
 59      cv = 0 ; 
 60      for(int i = 1;i <= tt;i ++)
 61      {
 62          if(k < prime[i] || k == 1)
 63              return cv;
 64          if(k % prime[i] == 0)
 65          {
 66             if(mp.find(prime[i]) != mp.end())
 67                 cv +=status;
 68             else cv -=status ;
 69             k /= prime[i];
 70             i--;
 71          }
 72      }
 73      if(mp.find(k) != mp.end())
 74          cv+=status;
 75      else cv -=status;
 76      return cv;
 77 }
 78 int gcd(int a, int b)
 79 {
 80   return b == 0?a:gcd(b,a%b);
 81 }
 82 int gcdv[maxn];
 83 int dv[maxn];
 84 int main(){
 85     sai();
 86     scanf("%d %d",&n,&m);
 87     for(int i = 1;i <= n;i++ )
 88     {
 89       scanf("%d",&a[i]);
 90     }
 91     for(int i = 1;i <= m;i ++)
 92     {
 93         scanf("%d",&b[i]);
 94         mp.insert(b[i]);    
 95     }
 96     gcdv[0] = a[1];
 97     dv[0] = solve(a[1],1);
 98     for(int i = 1;i <= n;i ++)
 99     {
100         gcdv[i] = gcd(gcdv[i-1],a[i]);
101         if(gcdv[i] == gcdv[i-1])
102         {
103           dv[i] = dv[i-1];
104         }else{
105           dv[i] = solve(gcdv[i],1);
106         }
107     }
108 /*    for(int i = 1;i <= n;i ++)
109         printf("%d ",gcdv[i]);
110     printf("
");
111     for(int i = 1;i <= n;i ++)
112         printf("%d ",dv[i]);
113     printf("
");
114 */    int ok = 0  ; 
115     int tmpgcd = 1; 
116     int ans = 0 ; 
117     for(int i = n;i >= 1;i --)
118     {
119        if(ok)
120        {
121            if(gcdv[i] != gcdv[i+1])
122            {
123                 int tmp = solve(gcdv[i]/tmpgcd,1);
124                 //printf("***%d %d %d
",gcdv[i],tmpgcd,gcdv[i]/tmpgcd);
125                 if(tmp > 0)
126                 {
127                    tmpgcd = gcdv[i]    ;
128                 }
129            }
130        }else{
131           if(dv[i] > 0 )
132           {
133             ok = 1; 
134             tmpgcd = gcdv[i];
135           }
136        }
137        //printf("%d 
",tmpgcd);
138        ans += solve(a[i]/tmpgcd,-1);
139     }
140     //printf("%d
",si);
141     printf("%d
",ans);
142 return 0;
143 }

View Code

没有梦想，何谈远方