Codeforces #1248A Integer Points题解（Java）

• • 题目大意：
  • 输入：
  • 输出：
  • 数据范围：
  • 思路
  • 代码

题目链接

题目大意：

已知有n条形如y=x+pi (i=1,2,3,…,n)的直线和m条形如y=-x+qi(i=1,2,3,…,m)的直线，问有几个横纵坐标均为整数的交点，输出个数。

输入：

第一行输入一个整数t表示有t组测试数据

每一组测试数据的第一行输入一个整数n表示有n条形如y=x+pi的直线

第二行输入n个数代表p1,p2,p3,…,pn

第三行输入一个整数m表示有m条形如y=-x+qi的直线

第四行输入m个数代表q1,q2,q3,…,qm

输出：

每组数据输出一个数表示横纵坐标均为整数的交点个数。

数据范围：

t(1<=t<=1000) n(1<=n<=105) pi(1<pi<=109) m(1<=m<=105) qi(1<=qi<=109)

思路

我们来推算一下交点的方程

x+pi=-x+qi

2x=qi- pi

x=(qi- pi)/2

我们会发现如果(pi-qi)是个偶数，那么这个交点的横纵坐标就都是整数

也就是(pi-qi)%2==0,我们还可以推算出(pi+qi)%2==0,那么我们只需要求出两条直线的纵截距相加是奇数还是偶数。

我们知道奇数+奇数=偶数，奇数+偶数=奇数，偶数+偶数=偶数。

所以我们只要求出pi和qi分别奇数和偶数的个数然后答案就是他们奇数个数相乘加上他们偶数个数相乘。

代码

import java.util.Scanner;

public class Main {
    public static void function(long a_odd,long a_even,long b_odd,long b_even){
        long sum=a_odd*b_odd+a_even*b_even;
        System.out.println(sum);
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        long t;
        long n,m;
        t=scanner.nextLong();
        for (long i=0;i<t;i++){
            long a_odd=0;
            long a_even=0;
            long b_odd=0;
            long b_even=0;
            n=scanner.nextLong();
            for (long j=0;j<n;j++){
                if(scanner.nextLong()%2==0)a_even++;
                else a_odd++;
            }
            m=scanner.nextLong();
            for (long j=0;j<m;j++){
                if(scanner.nextLong()%2==0)b_even++;
                else b_odd++;
            }
            function(a_odd,a_even,b_odd,b_even);
        }
    }
}