[cf] 594 div2 A - Integer Points

前言

t a g : tag : tag: 线段交点 数学分析 乘法原理 *1000

传送门:

题意 : 给定 n , m n,m n,m分别表示 p [ ] , q [ ] p[],q[] p[],q[]的大小

询问了两条直线 y = x + p [ i ] y=x+p[i] y=x+p[i]和 y = − x + q [ i ] y=-x+q[i] y=−x+q[i]有多少个 横坐标 是 整数的 交点

思路 : 根据题意求出 x x x表达式 x + p [ i ] = − x + q [ i ] x+p[i]=-x+q[i] x+p[i]=−x+q[i] 2 x = q [ i ] − p [ i ] 2x=q[i]-p[i] 2x=q[i]−p[i] x = ( q [ i ] − p [ i ] ) / 2 x=(q[i]-p[i])/2 x=(q[i]−p[i])/2

显然当且仅当 q [ i ] q[i] q[i]和 p [ i ] p[i] p[i]同奇偶的时候才可能是整数解

显然我们根据乘法原理可知,最终答案就是 p 奇 数 ∗ q 奇 数 + p 偶 数 ∗ q 偶 数 p奇数*q奇数+p偶数*q偶数 p奇数∗q奇数+p偶数∗q偶数 code :

int n,m;
int a[N],b[N];
void solve(){
	int aodd = 0 ,aeven = 0 ;
	int bodd = 0 ,beven = 0;
	
	cin>>n;
	for(int i=1;i>a[i];
		if(a[i]&1) aodd ++;
		else aeven ++;
	}
	
	cin>>m;
	for(int i=1;i>b[i];
		if(b[i]&1) bodd++;
		else beven ++;
	}
	
	cout