首页 > 代码库 > zoj Treasure Hunt IV

zoj Treasure Hunt IV

Treasure Hunt IV

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 from b 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 <= 263-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

 

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<math.h>
 6 using namespace std;
 7 typedef unsigned  long long LL;
 8 
 9 LL solve(LL n)
10 {
11     LL m = (LL)sqrt(n*1.0);
12     LL sum=0;
13     if(m%2==0) sum = n-m*m;
14     if(m%2==1) m++;
15     LL j=m/2;
16     sum=sum-j+2*j*j;
17    // sum=sum+2*j*j-j;
18     return sum;
19 }
20 int main()
21 {
22     LL n,m;
23     while(scanf("%llu%llu",&n,&m)>0)
24     {
25         n++,m++;
26         LL ans=solve(n-1);
27         LL cur =solve(m);
28         printf("%llu\n",cur-ans);
29     }
30     return 0;
31 }