P9231 [藍橋杯 2023 省 A] 平方差 - 洛谷

題目描述

給定?L,R，問?L≤x≤R?中有多少個數?x?滿足存在整數?y,z?使得?x=y2?z2。

輸入格式

輸入一行包含兩個整數?L,R，用一個空格分隔。

輸出格式

輸出一行包含一個整數滿足題目給定條件的?x?的數量。

輸入輸出樣例

輸入 #1	輸出 #1
1 5	4

說明/提示

【樣例說明】

• 1=12?02
• 3=22?12
• 4=22?02
• 5=32?22

【評測用例規模與約定】

• 對于 40% 的評測用例，L,R≤5000；
• 對于所有評測用例，1≤L≤R≤109。

第十四屆藍橋杯大賽軟件賽省賽 C/C++ 大學 A 組 C

思路：

數學知識，

1. 奇偶性分析：

   • 情況 1：y?和?z?都是奇數或都是偶數
     • 如果?y?和?z?都是奇數或都是偶數，那么?y?z?和?y+z?的奇偶性相同。
     • 兩個奇數或兩個偶數相減和相加的結果都是偶數。
     • 因此，x?是兩個偶數的乘積，即?x?是 4 的倍數。
   • 情況 2：y?和?z?一奇一偶
     • 如果?y?和?z?一奇一偶，那么?y?z?和?y+z?都是奇數。
     • 兩個奇數相乘的結果是奇數。
     • 因此，x?是兩個奇數的乘積，即?x?是奇數。

從上述分析可以看出，無論?y?和?z?的奇偶性如何，x=(y?z)×(y+z)?總是可以表示為兩個奇偶性相同的數的乘積：

• 如果?y?和?z?的奇偶性相同，x?是兩個偶數的乘積（即 4 的倍數）。
• 如果?y?和?z?的奇偶性不同，x?是兩個奇數的乘積（即奇數）。

因此，表達式?x=(y?z)×(y+z)?保證了?x?可以被拆分成兩個奇偶性相同的數的乘積。

代碼如下：
?

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll; 
ll j(ll x)
{if(x == 0)return 0;elsereturn (x+1)/2;
}
ll o(ll x)
{return x/4;
}
int main() 
{ll l,r;cin >> l >> r;cout << j(r) - j(l - 1) + o(r) - o(l - 1); return 0;
}