洛谷 P1348 Couple number
题目描述
任何一个整数N都能表示成另外两个整数a和b的平方差吗?如果能,那么这个数N就叫做Couple number。你的工作就是判断一个数N是不是Couple number。
输入输出格式
输入格式:
仅一行,两个长整型范围内的整数$n_1$和$n_2$,之间用1个空格隔开。
输出格式:
输出在$n_1$到$n_2$范围内有多少个Couple number。
注意:包括$n_1$和$n_2$两个数,且$n_1<n_2,n_2 - n_1 \leqslant 10^7$。
输入输出样例
输入样例#1:
1 10
输出样例#1:
7
感想
离高考还有46天,为纪念省统测考得不错,忙里偷闲来做一道题#滑稽。
前几天Neil出YNOI2018时没叫上我,自己一个人就把题目出好发给老师了……说好的一起出今年省选题呢!?
发现自己的码力在不断地降降降降……这道普及减的题花费了我两晚上(见下)……
解题思路(雾)
第一晚,打表找规律——
#include<cstdio> int p[]={};
int pf[]={};
int main()
{
for(int i=;i<=;i++)
pf[i]=i*i; for(int i=;i<=;i++)
for(int j=;j<i;j++)
p[pf[i]-pf[j]]=; for(int i=1;i<=;i++)//我居然还记得这样可以既去重又排序#滑稽
if(!p[i]) printf("%d\n",i); return ;
}
运行结果的最前面一部分——
随着$n$的增大,$n^2$和$(n-1)^2$的差距只会越来越大,这些在一万以内无法用平方差表示的数,一万以上的数的平方差更表示不了,所以基本可以确定这些就是答案要排除的数了。可以看到,这些数按顺序排成数列,是以2为首项,4为公差的等差数列,那么我们只需判断$a$到$b$的范围内有多少个数字不在这个数列当中。
第二晚——写暴力。无疑有$O(1)$的算法,还不难,但是本蒟蒻凑了好久都凑不出来,留坑到高考以后算了(逃),那就先写个$O(n)$的暴力把这题A了再说吧——
#include<cstdio> int main()
{
int a,b;
scanf("%d%d",&a,&b);
int ans=;
for(int i=a;i<=b;i++)//水平下降的标志
{
if((i-)%) ans++;
}
printf("%d",ans);
return ;
}
至于证明,感觉可以用数列$a_n=n^2$的差分数列为$b_n=2n+1$来证,答案的意思就是,$[a,b]$内有多少个数字能表示成$b_n$的一段区间和,然后……留坑到高考以后吧
最新文章
- AI中去掉页面边框
- sql常识-IN 操作符
- Android TextView中实现点击文本超链接(无下划线)的封装类
- 在QuartusII 中使用tcl对工程进行复制——半自动
- 拓展自定义编辑器窗口(EditorGUILayout类)
- 201521123079 《Java程序设计》第1周学习总结
- 顺便说说webservice
- 152. Maximum Product Subarray(中等, 神奇的 swap)
- Office2010安装出现“错误1907”的解决方法(未验证)
- 河北大学python选修课00次作业
- React-Native 问题随记2: com.android.builder.testing.api.DeviceException
- Educational Codeforces Round 8 B. New Skateboard
- L245
- mysql基础知识(1)
- Vysor安装图解
- sql 的理解
- UGUI Auto Layout 自动布局
- springcloud11----turbine
- 破解ZendStudio 10.1
- wpf path语法