2020-2021:teams:farmer_john:bazoka13_educational_codeforces_round_89_rated_for_div._2
A、B、C
- 手速题
D
- 题意：对于给定的数字$a[i]$，判断其是否存在两个不为$1$的因子，其和与$a[i]$互质
- 题解：筛一下，然后将$a[i]$分解为$b_1^{p_1}+b_2^{p_2}+\ldots$的形式，取$d_1=b_1^{p_1},d_2=a[i]/d_1$
- 证明：$x,y互质时，gcd(x+y,xy)=1$
- $gcd(x,y)=1\rightarrow gcd(x+y,x)=gcd(x+y,y)=1$
- $gcd(x+y,xy)=gcd(x+y,x)=1$
E
- 题意：$b$是有$m$项的严格递增的单调数列，将$a$分成$m$部分，使得第$i$部分的最小值等于$b[i]$,输出方案数
- 题解：由于$b$是严格递增的，那么可以考虑求出$a$的后缀最小值，以此确定每部分可能的起点和终点，并在相应$b$的编号上$+1$，最后求积即可
2020-2021/teams/farmer_john/bazoka13_educational_codeforces_round_89_rated_for_div._2.txt · 最后更改: 2020/06/12 22:40 由 bazoka13
