Problem : 187 - 小學老師

Problem Statistics

Solved Member: 7　　Submission: 24　　User Tried: 8

Statement:

定義f(a)為1到a-1(含)中最小不整除a的數字，若此數字不存在則f(a)=1。

而lolipop(a) = lolipop(f(a)) + 1，試求lolipop(A)+lolipop(A+1)+...+,lolipop(B)。

/*
某条是hh國小的小學老師，他現在在上數學課。

某条很有耐心的要教蘿莉算數，為此對每個蘿莉賦予一個編號，某条會跟a蘿莉從[1, a-1]找出最小不整除她編號的數字f(a)，並獎勵她(給她棒棒糖+健達出奇蛋+牛奶)，找不到f(a)的蘿莉很可憐，所以某条還是會給她一次獎勵。

因為編號越大的蘿莉越辛苦，所以某条會獎勵她比編號f(a)的蘿莉多1次。

定義lolipop(a)為獎勵蘿莉a的次數，則我們可以輕鬆lolipop(a) = 1 + lolipop(f(a))。

某条現在要教編號為A到B的蘿莉，請問某条要先準備好多少份獎品?
*/

Input:Output:

輸入檔會有多筆測資，每筆測資一行，請讀到EOF為止。
每筆測資佔一行，每行有兩個數字，依序為 A,B(3 ≤ A < B < 10¹⁷)。

每筆測資請輸出獨立一行，代表所求的答案。

Sample Input:Sample Output:

SAMPLE A:
3 6

SAMPLE B:
100 200

SAMPLE A:
11

SAMPLE B:
262

HINT:

10%的測資滿足: A,B ≤ 400
20%的測資滿足: A,B ≤ 1000000

For Sample A:

f(2) = 無， lolipop(2) = 1
f(3) = 2 ， lolipop(3) = 2
f(4) = 3 ， lolipop(4) = 3
f(5) = 2 ， lolipop(5) = 2
f(6) = 4 ， lolipop(6) = 4

Source:

COCI 2012/2013 #1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10