ROG

用户名：dotcpp0688243

访问量：5532

签　名：

等　　级
排　　名	2449
经　　验	2314
参赛次数	0
文章发表	8
年　　龄	0
在职情况	学生
学　　校	广东技术师范大学
专　　业	数字媒体技术

　　自我简介：

TA的其他文章

团伙--详细解答(不知道怎么处理敌人关系的进来）
浏览：128

你可能喜欢

C二级辅导-公约公倍（C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

Tom数（C语言代码）

优质题解

不用规律就超时（超时的进来）---C代码实现(规律证明——详细过程）

　　作者: ROG　　　　发表时间：2023-10-25 14:25:16 浏览：4895　|　评论：9　

原题链接：蓝桥杯2023年第十四届省赛真题-平方差

解题思路:

如果用当纯的数学公式一个一个代入计算，必定超时

所以只能找规律（该数是4的倍数或者该数是奇数）

如图： _-1569185504__bb0f7607d6b1b4bc14832308f48287dd_-1041684922_Screenshot_20231025_122043_Samsung Notes_0_wifi_0.jpg

这个规律的代码实现：

int sum = 0;
	long long L = 0;
	long long R = 0;
	scanf("%d %d", &L, &R);
	for(int i=L;i<=R;i++)
	{
		for(int j=1;j<=sqrt(i);j++)//找因子
		{
			if(i%j==0)//j是不是该数的因子
			{
				long long y = i / j;
				if (y%2==0&&j%2==0||y%2!=0&&j%2!=0)//这对因子的奇偶性是否相同
				{
					sum++;
					break;
				}
			}
			
			
			
		}
		
	}
	printf("%d", sum);

但是范围一大就会超时。所以要优化：

怎么优化呢？？？？？

从图得出的规律进一步总结：

1、当该数的一对因子都是偶数时，这对因子分别是2的倍数，即一个因子%2==0，所以一对因子就相当于该数%4==0，即是4的倍数

2、当该数的一对因子都是奇数时，由数学知识得：奇数*奇数=奇数，可推出，该数为奇数。

3、综上所述：一个数有平方差，就是该数是4的倍数或者该数是奇数

注意事项:

1、接收范围的变量的数据类型是int，不要用long long会超时

参考代码:

#include  
void test90()
{
    int sum = 0;
    int  L = 0;
    int  R = 0;
    scanf("%d %d", &L, &R);
    for(int i=L;i<=R;++i)
    {
        if(i%4==0||i%2!=0)
        {
            sum++;
  
        }
    }
    printf("%d", sum);
  
}
int main()
{
test90();
    return 0;
}

0.0分

92 人评分