生物芯片
通过分析可知,每个灯泡是否亮灭与其因子数有关,当因子数为奇数时灯灭，为偶数时灯亮.
所以最直观的想法就是将区间[l~r]中的所有因子筛出来并记录其有多少个因子.其时间复杂度为O(n*(ai^1/2))n为区间长度,ai为区间中的每个数.当n比较大时必然超时！并且即使是用约数个数的公式也会超时，因为约数公式需要先筛质数，其复杂度为O(n),当n>=1e8时仍会超时.

本题我的做法是打表+找规律;
2 1
3 1
4 0
5 1
6 1
7 1
8 1
9 0
10 1
11 1
12 1
13 1
14 1
15 1
16 0
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 0
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 0
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 0
50 1
51 1
52 1
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60 1
61 1
62 1
63 1
64 0
65 1
66 1
67 1
68 1
69 1
70 1
71 1
72 1
73 1
74 1
75 1
76 1
77 1
78 1
79 1
80 1
81 0
82 1
83 1
84 1
85 1
86 1
87 1
88 1
89 1
90 1
91 1
92 1
93 1
94 1
95 1
96 1
97 1
98 1
99 1
100 0
这是前100个数的每个数的因子的奇偶情况(不含1),通过观察,我们可以发现第n个因子数为偶的的数的位置在(1+n^2+2*n)处。所以先找到前l个数和前r个数中的因子数为偶数的个数，两者做差就是[l~r]中因子数为偶数的数的个数(即灭的灯的个数),让区间长-灭的灯的数的个数就是亮的灯的数的个数。

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e3;

//第k个暗位出现在(1+n^2+n)位

ll n,l,r;
int res;

int main()
{
  cin>>n>>l>>r;
 ll s1=1,s2=1,sum1=0;
  while(s1*s1+2*s1+1<=r) s1++;//找到前r个数中因子数为偶数的数的个数
  while(s2*s2+2*s2+1<l) s2++;

   s1-=1;
  sum1=s1-s2+1;
  cout<<(r-l+1)-sum1;
  return 0;
}