d312. 抓兔子
標籤 :
通過比率 : 94人/110人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-06-04 00:55

內容
沉寂了好一段時間,腦袋裡裝滿著奇妙思想的Haruhi又有驚人之舉,這一次,她要抓兔子!

不過兔子是一種很精靈也很愛亂跳的動物,用普通的方法實在是沒有辦法抓到,所以需要製作陷阱來捕捉。

當然Haruhi是不可能親自做這種無聊的工作,而一切的麻煩就落在了Kyon的頭上...

Kyon花了好一段時間觀察兔子的行動模式:在一條正向的數線上,兔子會從座標為k(k >= 2)的兔子窟中出現,然後每次往正軸跳k格,例如k = 2時,兔子會先從x = 2的地方出現並每次往正向跳2格,到x = 4, x = 6, x = 8...的地點,而Kyon的陷阱就是要放置在這些兔子會跳到的點上。

不過兔子窩不是每個座標上都有的,只有在兔子無論怎麼跳都跳不到的座標上才會有兔子窩出現,例如x = 2或x = 3等等地方,至於x = 4由於可以從x = 2跳過來,所以不會有兔子窩。而在兔子窩上是無法放置陷阱的。

為了防止世界被破壞、為了守護世界的和平,Kyon知道他無論如何一定要抓到兔子,不然惹Haruhi生氣,然後.......。

可是製作這麼多陷阱實在是太過於麻煩了,他想知道在x = a和x = b之間究竟有幾個座標點不需要放置陷阱。至於這個計算的工作,因為Kyon忙著做陷阱,所以就要交到身為他好友的你身上了!
輸入說明

第一行有一個正整數T,代表接下來有幾個詢問

接下來每行有兩個正整數a,b,代表詢問在a,b之間有幾個座標點不需要放置陷阱

我們保證:

至少30%的測試資料中a,b<=1000

至少60%的測試資料中a,b<=100000

所有的測試資料中1<a,b<=10000000

所有的測試資料中1<=T<=100

 

輸出說明
一個整數代表究竟有幾個座標點不需要放置陷阱。
範例輸入 #1
3
1 10
100 1
11 100
範例輸出 #1
4
25
21
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1M
提示 :
標籤:
出處:
[管理者: shik (shik) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」