【7.28】代码源 - 【Fence Painting】【合适数对（数据加强版）】

#735. Fence Painting

题意：有编号从 $1$ 开始的 $n(1\le n\le 10^5)$ 块木板， 第 $i$ 块木板的颜色是 $a_i$，你希望把第 $i$ 块木板的颜色染成 $b_i$ 。

有 $m$ 个画家会依次来工作，第 $j$ 个画家会把某一块木板染成颜色 $c_j$ ，你可以指定他们染哪一块，但是不能不染。

判断能否把所有木板都染成目标颜色，如果能，输出方案

思路：典中典的时间倒序处理。对于 $b$ 序列，我们按照 $b_i$ 进行分组。对于 $c_i$ ，如果在 $b_i$ 中存在对应颜色，我们肯定优先去染需要改变的地方，然后是不需要改变的地方。如果没有对应的颜色，只能去找一个染过色的地方（在时间正序中它会被后来的颜色覆盖掉），找不到的话肯定无解。

AC代码：http://oj.daimayuan.top/submission/306521

---

#733. 合适数对（数据加强版）

题意：给定一个长度为 $n(1\le n\le 10^6)$ 的正整数数列 $a(1\le a_i\le 10^7)$ 和一个正整数 $k(1\le k\le 100)$。 请你判断共有多少个数对 $(l,r)$ 满足：

$1\le l<r\le n$，存在一个整数 $x$ 使得 $a_l\times a_r=x^k$ 成立

题解：(质因数分解)代码源每日一题 Div1 合适数对（数据加强版)

思路：首先，乘积为正整数的 $k$ 次方，从质因子的角度来看，乘积每个质因子的次数一定是 $k$ 的倍数。那我们让每个数的质因子的次数对 $k$ 取余，如果两个数每个质因子的次数和加起来都是 $0$ 或 $k$ ，那么一定是满足的一对数。

那么处理方法就是：把每个数处理为质因子模 $k$ 的乘积，然后存到桶里。由 $a_r$ 求 $a_l$ 也很简单。这道题常数卡的很严，模数和被模数都要开 int ，这样模的速度比 LL 稍快一些。

这里学到了一个新的筛质数方法，比 之前的 更优：

• 预处理所有数的最小质因子，然后只用质因子去筛，时间复杂度 $O(n\sim \log n)$

while(num > 1){
    
	int cnt = 0, m = minp[num];
	while(num % m == 0) cnt ++ , num /= m;
	// m ^ cnt
}

AC代码：http://oj.daimayuan.top/submission/308329