Square Numbers

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <stdio.h>
 5 #include <cstring>
 6 #include <string>
 7 #include <cstdlib>
 8 #include <queue>
 9 #include <stack>
10 #include <set>
11 #include <vector>
12 #include <map>
13 #include <list>
14 #include <iomanip>
15  #include <fstream>
16 using namespace std;
17 
18 int ans[100003];
19 //bool check[10001][10001];
20 //const long n=100000; 
21 void db()
22 {
23     int cnt=0;
24     int t;
25     for(int i=100000;i>=1;--i)
26     {
27         t=sqrt(i);
28         if(t*t==i)
29             cnt++;
30         ans[i]=cnt;
31     //    printf("%d: %d
",i,cnt);    
32     }
33 } 
34 
35 int main()
36 {
37     int a,b;
38     db();
39     while(scanf("%d%d",&a,&b))
40     {
41         if(a==b&&b==0)
42             break;
43         printf("%d
",ans[a]-ans[b+1]);
44     }
45     return 0;
46 }

View Code

感觉是没啥技术含量的打表题，虽然之前有接触过，不过那个时候不知道这玩意儿叫前缀和，也不至于说不学也知道这个道理。。。。