[蓝桥杯 2023 省 A] 平方差

题目链接

[蓝���杯 2023 省 A] 平方差

（）

题目描述

给定 L , R L,R L,R，问 L ≤ x ≤ R L \leq x \leq R L≤x≤R 有多少个 x x x 满足存在整数 y , z y,z y,z 使得 x = y 2 − z 2 x = y^2 - z^2 x=y2−z

输入格式

输入一行包含两个整数 L , R L,R L,R，用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 x x x 的数量。

输入输出样例

输入

1 5

输出

4

（）

说明/提示

• 1 = 1 2 − 0 2 1 = 1^2 - 0^2 1=12−02
• 3 = 2 2 − 1 2 3 = 2^2 - 1^2 3=22−12
• 4 = 2 2 − 0 2 4 = 2^2 - 0^2 4=22−02
• 5 = 3 2 − 2 2 5 = 3^2 - 2^2 5=32−22

  数据范围

  • 1 ≤ L , R ≤ 1 0 9 1 \leq L,R \leq 10^9 1≤L,R≤109

    解法：数学 + 找规律

    对于原式 x = y 2 − z 2 x = y^2 - z^2 x=y2−z2，可以转换为 x = ( y + z ) ( y − z ) x = (y + z)(y-z) x=(y+z)(y−z)，令 a = y + z , b = y − z a = y + z, b = y - z a=y+z,b=y−z，即 x = a × b x = a \times b x=a×b。

    因为 a − b = ( y + z ) − ( y − z ) = 2 z a - b = (y + z) - (y - z) = 2z a−b=(y+z)−(y−z)=2z。

    所以 a a a 和 b b b 之差一定是偶数，所以 a , b a ,b a,b 只能是 奇数和奇数 或者 偶数和偶数。

    1. a , b a,b a,b 都是 奇数 的情况：

    a , b a,b a,b 都是奇数，那么 a × b a \times b a×b 也是奇数，所以 x x x 也是奇数，那么 [ L , R ] [L,R] [L,R] 范围内的奇数都满足条件。

    2. a , b a,b a,b 都是 偶数 的情况：

    a , b a,b a,b 都是偶数，那么 a × b a \times b a×b 也是偶数并且是 4 4 4 的倍数，所以 x x x 也是 4 4 4 的倍数，那么 [ L , R ] [L,R] [L,R] 范围内的 4 4 4 的倍数都满足条件。

    如果要求 [ 1 , n ] [1,n] [1,n] 范围内的 奇数 个数，那就是 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n​⌉。

    举例，有 n u m s [ 9 ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } nums[9] = \{ 1,2,3,4,5,6,7,8,9 \} nums[9]={1,2,3,4,5,6,7,8,9}，那么奇数个数就为 ⌈ 9 2 ⌉ = 5 \lceil \frac{9}{2} \rceil = 5 ⌈29​⌉=

    如果要求 [ 1 , n ] [1,n] [1,n] 范围内的 4的倍数 个数，那就是 ⌊ n 4 ⌋ \lfloor \frac{n}{4} \rfloor ⌊4n​⌋。

    举例，有 n u m s [ 9 ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } nums[9] = \{ 1,2,3,4,5,6,7,8,9 \} nums[9]={1,2,3,4,5,6,7,8,9}，那么4的倍数个数就为 ⌊ 9 4 ⌋ = 2 \lfloor \frac{9}{4} \rfloor = 2 ⌊49​⌋=

    如此我们就可以定义一个函数 f u n ( i ) fun(i) fun(i)，求出 [ 1 , i ] [1,i] [1,i] 区间内所有满足条件的 x x x 的数量 ，最终返回的答案就是 f u n ( R ) − f u n ( L − 1 ) fun(R) - fun(L-1) fun(R)−fun(L−1)。

    时间复杂度： O ( 1 ) O(1) O(1)

    C++代码：

    #include 
    using namespace std;
    int fun(int x){
        return (x + 1) / 2 + x / 4;
    }
    int main(){
        int l, r;
        cin>>l>>r;
        
        int ans = fun(r) - fun(l - 1);
        cout
    	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	static int n;
    	
    	public static int fun(int x) {
    		return (x + 1) / 2 + x / 4;
    	}
    	
    	public static void main(String[] args) throws Exception 
    	{
    		int l;
    		int r;
    		String[] str = in.readLine().split(" ");
    		l = Integer.parseInt(str[0]);
    		r = Integer.parseInt(str[1]);
    		
    		int ans = fun(r) - fun(l - 1);
    		
    		System.out.println(ans);
    	}
    }