[7.28] Code Source - [Fence Painting] [Appropriate Pairs (Data Enhanced Version)]

#735. Fence Painting

题意：有编号从 $1$ 开始的 $n(1\le n\le 10^5)$ 块木板, 第 $i$ The color of the boards is $a_i$,you want to put the $i$ The color of the boards is dyed $b_i$ .

有 $m$ Each painter will come to work in turn,第 $j$ A painter will dye a certain board a color $c_j$ ,You can specify which piece they dye,But can not be stained.

Determine if all boards can be dyed the target color,如果能,输出方案

思路：The time-reversed processing of the dictionary.对于 $b$ 序列,我们按照 $b_i$ 进行分组.对于 $c_i$ ,如果在 $b_i$ There are corresponding colors in ,We definitely prioritize dyeing where things need to be changed,Then there are the places that don't need to be changed.If there is no corresponding color,Just find a place that has been dyed（In positive chronological order it will be overwritten by later colors）,If you can't find it, it's definitely a no-brainer.

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 合适数对（数据加强版)

思路：首先,The product is a positive integer $k$ 次方,From the point of view of prime factors,The degree of multiplying each prime factor must be $k$ 的倍数.Then we make the degree pairs of the prime factors of each number $k$ 取余,If the sum of the degrees of each prime factor of two numbers is $0$ 或 $k$ ,Then it must be a satisfying pair of numbers.

Then the way to deal with it is：Treat each number as a prime factor modulo $k$ 的乘积,Then store it in a bucket.由 $a_r$ 求 $a_l$ 也很简单.This question is very strict,Both the modulo and the modulo are turned on int ,The speed ratio of this mode LL 稍快一些.

Learned here a new sieve prime number method,比 之前的 更优：

• The smallest prime factor that preprocesses all numbers,Then just use the prime factor to sieve,时间复杂度 $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