于CF1080_E题遇到对欧拉筛的活用，从新总结用法及原理
欧拉筛
欧拉筛/线性筛：核心是利用一个质数筛掉其他合数
动态规划的思想
任何一个合数C，能且只能被分解为唯一的 $C=i \cdot p_{min}$ ,其中 $p_{min}$ 是C的最小质因数，i是某个确定的整数。
算法外层循环遍历所有整数i，内层循环从小到大遍历已知质数集合p。我们把 $i \cdot p_{min}$ 当作已知的合数，把他标记为被筛出。
外层遍历i的过程中，若i是合数，那么其一定可以被分解为比自己小的倍数$i_{last}$与比他小的素数的积(比他小保证了在遍历到他之前已经被处理过)，其会在处理i之前被处理为is_prime[$p_{min}*i_{last}$]=1；反之则说明其不是合数，我们直接将其添加到is_prime中即可
最关键的逻辑： if(i%p==0) break;
当i%p==0成立时，意味着质数p已经是整数i的质因数之一，且由于我们从小到大遍历质数，p就是i的最小质因数。此时我们不难考虑到，此时如果再进行合数的计算，就使得 $p_{next} \cdot i$ 的最小质因数不再是 $p_{next}$ 而是p，不满足我们在前面设定的最小质因数的合数条件，故break，等待后面的遍历来计算，防止重复。
欧拉筛模板代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> primes;
bool is_prime[1000005];
void count_primes(){
for(int i=2;i<=1000005;i++){
if(!is_prime[i])
primes.push_back(i);
for(auto p:primes){
if(i*p>1000005) break;
is_prime[i*p]=1;
if(i%p==0) break;
}
}
}
primes存所有质数，is_prime用位置的值反应是否是素数，0是素数，1是合数。
|
E. Divisive Battle
对本题而言，题目核心及解出数列内的数的最小素因数和最大素因数，关键在于理解，若当前数的不同的素因数个数大于1，则Alice必定胜利(分解后内部有序，故需判断两个相邻的数分解后是否保持有序)
对上述计量方法插入对最大最小素因数的统计，及统计其个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| int max_p[1000005];
vector<int> primes;
bool is_prime[1000005];
int min_p[1000005];
inline int gcd(int x,int y){
while(y){int t=x%y;x=y;y=t;}return x;
}
int cnt[1000005];//某个数的质数个数
void count_primes(){
min_p[1]=1;
max_p[1]=1;
cnt[1]=0;
for(int i=2;i<=1000000;i++){
if(!is_prime[i]){
primes.push_back(i);
min_p[i]=i;
max_p[i]=i;
cnt[i]=1;
}
for(auto p:primes){
if(i*p>1000000) break;
is_prime[i*p]=1;
min_p[i*p]=p;
max_p[i*p]=max(max_p[i],p);
if(i%p==0){
cnt[i*p]=cnt[i];//可以不写，未来还会来处理
break;
}else{
cnt[i*p]=cnt[i]+1;
}
}
}
}
|
cnt[i]的计算是两种状态转移
A.当i%p==0,可以不做处理，当前产生的合数无法增加素因数个数
B.当i%p!=0，此时合数在i的素因数基础上再+p，及素因数个数+1
当我们先手一次性处理完之后，即可直接判断
1
2
3
4
5
6
7
8
9
10
11
| if(cnt[a[i]]>1){
cout<<"Alice"<<endl;
return;
}
//若某个数素因数个数多于1，直接判定Alice胜利
if(i<n && max_p[a[i]]>min_p[a[i+1]]){
cout<<"Alice"<<endl;
return;
}
//若在拆分过程中发现相邻两个数不满足拆分后素数last_max<=next_min,即不满足非递减，则Alice胜利
//除此之外，Bob胜利
|
