zoj 3629 Treasure Hunt IV(找规律)

Alice is exploring the wonderland, suddenly she fell into a hole, when she woke up, she found there are b - a + 1 treasures labled a fromb in front of her.
Alice was very excited but unfortunately not all of the treasures are real, some are fake.
Now we know a treasure labled n is real if and only if [n/1] + [n/2] + ... + [n/k] + ... is even.
Now given 2 integers a and b, your job is to calculate how many real treasures are there.

Input

The input contains multiple cases, each case contains two integers a and b (0 <= a <= b <= 2⁶³-1) seperated by a single space. Proceed to the end of file.

Output

Output the total number of real treasure.

Sample Input

0 2
0 10

Sample Output

1
6

一开始还考虑用欧拉定理算因子和什么的。。。
然后看到数据范围。。。噗。。显然不能那样做。。。
所以一开始看清楚数据范围是很重要的。  


这个数据范围应该就是找规律了。。。。
结果试着找了下。。。果然有规律hhhhh
需要注意的是要分奇偶。。。
如果是偶数可能会多算。。。因为这个wa了一发。。。

 1 /*************************************************************************
 2     > File Name: code/zoj/3629.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年10月24日 星期六 20时07分02秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<queue>
14 #include<vector>
15 #include<stack>
16 #include<cctype>
17                  
18 #define yn hez111qqz
19 #define j1 cute111qqz
20 #define ms(a,x) memset(a,x,sizeof(a))
21 using namespace std;
22 const int dx4[4]={1,0,0,-1};
23 const int dy4[4]={0,-1,1,0};
24 typedef long long LL;
25 typedef double DB;
26 const int inf = 0x3f3f3f3f;
27 LL a,b;
28 void pre()
29 {
30     int sum =  1;
31     for ( int i =1; i <= 300 ; i++)
32     {
33     int res = 0 ;
34     for ( int j = 1 ; j <= i ; j++)
35         res = res + i/j;
36     if (res%2==0)
37     {
38         sum++;
39         cout<<"i:"<<i<<endl;
40     }
41 
42     }
43 
44     printf(" sum: %d
",sum);
45 
46 }
47 
48 LL cal( LL n) //计算0到n有多少个数满足
49 {
50     if(n==0) return 1;
51     if (n<0) return 0;
52 
53     LL res = 0 ;
54     LL sn = sqrt(n);
55     LL k = sn/2 + 1; //k为等差数列的项数，第k项为4k-3
56     
57      res = (2*k-1)*k;
58      if (sn%2==0)
59     {
60     res = res -(4*k-3);
61     res = res+n-(2*k-2)*(2*k-2)+1;
62     }
63 
64   //  cout<<"k:"<<k<<" n:"<<n<<" res:"<<res<<endl;
65     return res;
66      
67 }
68 int main()
69 {
70   #ifndef  ONLINE_JUDGE 
71    freopen("in.txt","r",stdin);
72   #endif
73 
74    //pre();
75    while (scanf("%lld %lld",&a,&b)!=EOF)
76     {
77     printf("%lld
",cal(b)-cal(a-1));
78     }
79   
80    
81  #ifndef ONLINE_JUDGE  
82   fclose(stdin);
83   #endif
84     return 0;
85 }

View Code