洛谷 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时没叫上我，自己一个人就把题目出好发给老师了……说好的一起出今年省选题呢！？

　　发现自己的码力在不断地降降降降……这道普及减的题花费了我两晚上(见下)……

解题思路(雾)

　　第一晚，打表找规律——

 1 #include<cstdio>
 2 
 3 int p[10010]={0};
 4 int pf[110]={0};
 5 int main()
 6 {
 7     for(int i=1;i<=90;i++)
 8         pf[i]=i*i;
 9 
10     for(int i=1;i<=90;i++)
11         for(int j=0;j<i;j++)
12             p[pf[i]-pf[j]]=1;
13 
14     for(int i=1;i<=8100;i++)//我居然还记得这样可以既去重又排序#滑稽
15         if(!p[i]) printf("%d\n",i);
16 
17     return 0;
18 }

　　运行结果的最前面一部分——

 1 2
 2 6
 3 10
 4 14
 5 18
 6 22
 7 26
 8 30
 9 34
10 38
11 42
12 46
13 50
14 54
15 58
16 62
17 66
18 70
19 74
20 78
21 82
22 86
23 90
24 94
25 98
26 102
27 106
28 110
29 114
30 118
31 122
32 126
33 130
34 134
35 138
36 142
37 146
38 150
39 154
40 158
41 162
42 166
43 170
44 174
45 178

View Code

　　随着$n$的增大，$n^2$和$(n-1)^2$的差距只会越来越大，这些在一万以内无法用平方差表示的数，一万以上的数的平方差更表示不了，所以基本可以确定这些就是答案要排除的数了。可以看到，这些数按顺序排成数列，是以2为首项，4为公差的等差数列，那么我们只需判断$a$到$b$的范围内有多少个数字不在这个数列当中。

　　第二晚——写暴力。无疑有$O(1)$的算法，还不难，但是本蒟蒻凑了好久都凑不出来，留坑到高考以后算了(逃)，那就先写个$O(n)$的暴力把这题A了再说吧——

 1 #include<cstdio>
 2 
 3 int main()
 4 {
 5     int a,b;
 6     scanf("%d%d",&a,&b);
 7     int ans=0;
 8     for(int i=a;i<=b;i++)//水平下降的标志
 9     {
10         if((i-2)%4) ans++;
11     }
12     printf("%d",ans);
13     return 0;
14 }

　　至于证明，感觉可以用数列$a_n=n^2$的差分数列为$b_n=2n+1$来证，答案的意思就是，$[a,b]$内有多少个数字能表示成$b_n$的一段区间和，然后……留坑到高考以后吧