Problem : 327 - 兔子王國

Problem Statistics

Solved Member: 6　　Submission: 58　　User Tried: 6

Statement:

很久很久以前有個兔子王國，每隻兔子有一個兔值W_i，若兔子i與兔子j會打架，僅當他們兩個的兔值不互質。

現在有N隻兔子依序由1至n編號，現在有個競技場，國王很好奇，如果將第L隻到第R隻的兔子丟入競技場中，一共會有多少隻兔子完全不打架呢?

Input:Output:

一個測試資料檔案有多筆測試資料，請讀取至檔案結尾EOF。

對於每筆測試資料，第一行給定兩個數字N M，表示共有N隻兔子，M筆詢問，第二行有N個以空格隔開的數字W_i，接下來有M行，每行兩個數字L R，表示詢問將第L隻到第R隻的兔子丟入競技場中，一共會有多少隻兔子完全不打架。

限制：
1 ≤ N,M,W_i ≤ 200000
1 ≤ L ≤ R ≤ N

對於每筆詢問輸出一個數字於一行。

Sample Input:Sample Output:

3 2
2 1 4
1 2
1 3
6 4
3 6 1 2 5 3
1 3
4 6
4 4
2 6

2
1
1
3
1
2

Source:

ICPC Hangzhou 2013

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	3000ms	65536kb	100
1-2	3000ms	65536kb
1-3	3000ms	65536kb