The 19th Zhejiang University Programming Contest Sponsored by TuSimple (Mirror) B"Even Number Theory"（找规律？？？）

传送门

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题意：

　　给出了三个新定义：

1. E-prime : ∀ num ∈ E，不存在两个偶数a,b，使得 num=a*b;（简言之，num的一对因子不能全为偶数）
2. E-prime factorization : 定义集合P由 E-prime 元素组成，定义 e = p₁*p₂*.....*p_n；（p₁,p₂,....,p_n ∈ P , |P| = n）
3. E-factorial : 定义 e!! = 2*4*6*8*.........*e；（简言之，偶数e及其之前的偶数连乘积）

　　输出一个数 e ，求满足条件2的集合P，并且集合P需满足：p₁*p₂*.....*p_n = e!! , |P| = n；

　　求 n 的最大值；

 题解：

　　定义集合 P_i 为偶数 i 的满足条件（2）的最大的集合；

　　例如P₈ = {2,2,2}，| P₈ | = 3；

　　根据贪心的思想，要想使集合 P_e!! 中的元素个数最多，那么，e!! 一定要优先分解出最多的2（最小的e-prime）;

　　定义 odd 表示奇数，那么 odd*2 为 e-prime，因为 odd 因式分解肯定没有偶数因子，odd*2 只能分解出一个偶数因子2，符合条件（1）；

　　因此，对于所有的奇数 odd，可以通过让 odd*2 将 odd 转化为 e-prime，那么，我们的关注点就变成了 e!! 最多能分解出多少个2；

　　对于 e 之前的所有偶数，假设 ≤ e 的最大的2的幂为 2^x，那么对于 e 之前的所有2的幂 2¹,2²,2³,....,2^x 其可分解出 1+2+3+......+x 个2；

　　那 e 之前的所有非2的幂的偶数 even ，该如何快速求出他们的乘积最多能分解出多少个2呢？

　　首先考虑这一点，任何一个偶数 even 都可分解成 odd*2ⁱ 模式， 那么 |P_even | = i；

　　那么，我们反过来考虑，对于任意奇数 odd 都可通过 odd*2ⁱ 求出 | P_odd*2ⁱ | = i;

　　

　　　　　　（每两个相邻的2的幂间的偶数块用红色编号① ② ③ ④ ...........表示）

　　　　　　（紫色数字代表相邻的2的幂间的奇数的个数）

　　对于偶数块①：只有一个奇数 3；

　　3*2¹ 来到偶数块②；

　　3*2² 来到偶数块③；

　　3*2³ 来到偶数块④；

　　........

　　3*2^x-1来到偶数块(x)；

　　可知，通过3*2ⁱ 可求出P_3*2¹ , P_3*2² , .........., P_3*2^x-1，其集合元素总和为 1+2+3+..........+(x-1);

　　那么，对于偶数块 2 中的某一奇数 odd 呢？

　　根据对3的分析，可知，其可以构成的 ≤ 2^x+1 的最大的偶数为 odd*2^x-2 ，那么，通过 odd 求出的集合P_odd*2ⁱ 的元素总和为 1+2+3+.......+(x-2)

　　因为偶数块②有2¹个奇数，所以这些奇数可以求出的集合P的元素总和为 2*(1+2+3+........+(x-2) ）;

　　对于偶数块

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄