首页 > 代码库 > ZOJ 3629(找规律)

ZOJ 3629(找规律)

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 afrom 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

        额,找规律的题。看见 (0 <= a <= b <= 263-1) 时,就知道暴力会超时了,所以就找规律吧!

       先写一个暴力的程序打表,这样的事以前也做过,一个循环节为197的规律题,打表只到100,还以为够了,结果那题没找到规律,以后再做这样的事的时候,先打表到10000再详谈!

#include<stdio.h>
int main()
{
    freopen("呵呵.txt","w",stdout);
    int i;
    for (i=0; i<=1000; i++)
    {
        int ans=0;
        for (int j=1; j<=i; j++)
        {
            ans+=i/j;
        }
        if (ans%2==0)
            printf("%d\t",i);
    }
    return 0;
}

  [0^2,1^2)                   1

  [2^2,3^2)                   5

  [4^2,5^2)                   9

  [6^2,7^2)                  13

  [8^2,9^2)                  17

  [10^2,11^2)              21

  [12^2,13^2)              25

  . . . .

  . . . . . .