CF403B/CF402D-白红宇

CF403B/CF402D

阅读量：2496 次

发布时间：2019-05-11

本文共 2214 字，大约阅读时间需要 7 分钟。

原题题意说

给你一个n长度的数组 a ，保存了a1~an的n个数字。

再给你m个坏的质数b1~bm。

告诉你可以每次操作数组a中前r个元素，1<=r<=n，使得a[i] = a[i]/g，g是前r个元素的最大公约数。

问你经过任意次操作后，segma(f(ai))的最大值为多少。

我一开始对于f函数的意思不太懂，后来把他展开，就明白了。

当s=1，f=0；

当p是s的最小的约数（同时必然是质数）时，f=f(s/p)+g(p)

g函数是我临时加的，发现p为good时，g(p)= 1；p为bad时，g(p)= -1；

s=p时，f=f(1)+g(p)=0+g(p)，所以g就是f

那么得到 f 就是 s 中good数减去bad数。

发现好像可以搞了，只要前缀和一个数组 a 的 gcd 。

思路是贪心

从 n 开始向 1 扫，如果 i 的前缀和的gcd 的 f 小于 0，就把从1 到 i 的 gcd 通过变换消去，那么就可以使得整个数组的segma增加 f(gcd)，同时记录一下我变换消去的 gcd 的值，在下一次检查的时候要先用当前的gcd除以之前保存的这个记录下来的 gcd ，然后在判断是否 f 小于 0，也就是存在 good 数小于 bad数的这种情况。

好像还有一种动态规划的方法，，俄文看不懂，然后有兴趣的同学用谷歌翻译翻译成英文阅读，千万别翻译成中文阅读，那样是完全看不懂的。

我做的时候，看到 gcd 可以不保存直接用 gcd 的f 的效果是一样的，只要记录先前的gcd 的 f 在当前位置总共增加的值 cur ，在这一轮不要再重复增加到答案里面，然后 f 最后用map做一个映射，以加快速度， bad prime 就用set表示就好了。

其中最巧妙的就是处理f 的时候，一边分解s 的质因子一边计数这个过程。以及前面说了记录前缀 gcd 的 f 的值，和 cur。

上源代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         using namespace std;#define MaxN 5555const int maxn = 1000000;bool flag[maxn+5];int prime[maxn/3], TopPrime;int a[MaxN], bad[MaxN], gtf[MaxN];set 
         
           badSet;map 
          
            memo;void calc_prim(){ for(int i = 2; i <= maxn; i ++){ if(!flag[i]) prime[TopPrime++] = i; for(int j = 0; j < TopPrime && prime[j]*i <= maxn; j ++){ flag[i*prime[j]] = 1; if(i%prime[j]==0) break; } }}int F(int s){ if(s == 1) return 0; if(memo.find(s) != memo.end()) return memo[s]; int k = 0, ans = 0; int num = s; while(prime[k]*prime[k] <= s) { if(s % prime[k] == 0) { int isbad = badSet.count(prime[k]); while(s%prime[k] == 0) { s/=prime[k]; if(isbad) ans--; else ans++; } } k++; } if(s != 1) { if(badSet.count(s)) ans--; else ans++; } return memo[num] = ans;}int main(){// freopen("data.in", "r", stdin); calc_prim(); int n, m, G, cur, sum; scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } for(int i = 0; i < m; i++) { scanf("%d", &bad[i]); badSet.insert(bad[i]); } G = a[0]; sum = 0; for(int i = 0; i < n; i++) { int number = a[i]; sum += F(number); G = __gcd(number, G); gtf[i] = F(G); } cur = 0;//the F() of gcd been cut before for(int i = n-1; i >= 0; i--) { if(gtf[i] + cur < 0)//!!! { sum -= (gtf[i] + cur)*(i+1);//!!! cur += (gtf[i] + cur)/(-1); } } printf("%d\n", sum); return 0;}

转载地址：http://ibhrb.baihongyu.com/

你可能感兴趣的文章

RDIFramework.NET ━ .NET快速信息化系统开发框架 V2.7 版本发布