首页 > 代码库 > ZOJ 3629(找规律)
ZOJ 3629(找规律)
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
. . . .
. . . . . .