[cf] 767 div2 B. GCD Arrays

前言

t a g : tag : tag:gcd 数论 *800(看着不想800的啊 QAQ)
传送门 :

题意 :
给定 l , r , k l,r,k l,r,k询问是否可以操作最多 k k k使其满足条件

条件 :
对于 l , r l,r l,r确定的数组 a [ 1... ( r − l + 1 ) ] = { l , l + 1.... r } a[1...(r-l+1)] =\{l,l+1....r\} a[1...(r−l+1)]={l,l+1....r}

每次操作可以从中选取两个数 a [ i ] , a [ j ] a[i],a[j] a[i],a[j],删除这两个数,将这两个数的乘积加入数组中

当且仅当 g c d ( a ) > 1 gcd(a)>1 gcd(a)>1的时候满足条件

思路 :
因为 g c d ( 奇 数 , 偶 数 ) = 1 gcd(奇数,偶数) =1 gcd(奇数,偶数)=1因此我们考虑从 奇偶性入手

显然的 g c d ( 偶 数 , 偶 数 ) > = 2 gcd(偶数,偶数) >=2 gcd(偶数,偶数)>=2,同时又因为 奇 数 ∗ 偶 数 = 偶 数 奇数*偶数=偶数 奇数∗偶数=偶数

因此我们需要尽可能的消去 奇数, 因此我们只需要判断奇数的个数即可

code :

int n,m,k;

void solve(){
int l,r,k,num;
		cin>>l>>r>>k;
		if(l==r&&l!=1){
			cout