# [NOIP2005 普及組] 校門外的樹(shù)

## 題目描述

某校大門外長(zhǎng)度為 l?的馬路上有一排樹(shù)，每?jī)煽孟噜彽臉?shù)之間的間隔都是 1?米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸 0?的位置，另一端在 l的位置；數(shù)軸上的每個(gè)整數(shù)點(diǎn)，即0,1,2,...,l，都種有一棵樹(shù)。

由于馬路上有一些區(qū)域要用來(lái)建地鐵。這些區(qū)域用它們?cè)跀?shù)軸上的起始點(diǎn)和終止點(diǎn)表示。已知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹(shù)（包括區(qū)域端點(diǎn)處的兩棵樹(shù)）移走。你的任務(wù)是計(jì)算將這些樹(shù)都移走后，馬路上還有多少棵樹(shù)。

## 輸入格式

第一行有兩個(gè)整數(shù)，分別表示馬路的長(zhǎng)度 l?和區(qū)域的數(shù)目 m。

接下來(lái) m?行，每行兩個(gè)整數(shù) u, v，表示一個(gè)區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。

## 輸出格式

輸出一行一個(gè)整數(shù)，表示將這些樹(shù)都移走后，馬路上剩余的樹(shù)木數(shù)量。

## 樣例 #1

### 樣例輸入 #1

```
500 3
150 300
100 200
470 471
```

### 樣例輸出 #1

```
298
```

## 提示

**【數(shù)據(jù)范圍】**

• 對(duì)于?20%?的數(shù)據(jù)，保證區(qū)域之間沒(méi)有重合的部分。
• 對(duì)于?100%?的數(shù)據(jù)，保證 1≤l≤104，1≤m≤100，0≤u≤v≤l。

**【題目來(lái)源】**

NOIP 2005 普及組第二題

n,m=map(int, input().split())
ar=[1 for x in range(n+1)]  #生成0~n個(gè)共計(jì)n+1棵樹(shù)
for i in range(m):a,b=map(int,input().split())for j in range(a,b+1):ar[j]=0  #范圍內(nèi)挖掉的樹(shù)置0，若區(qū)間有重合也不過(guò)是重復(fù)置0
print(sum(ar))

題目描述

在一條無(wú)限長(zhǎng)的路上，有一排無(wú)限長(zhǎng)的路燈，編號(hào)為?1,2,3,4,…1,2,3,4,…。

每一盞燈只有兩種可能的狀態(tài)，開(kāi)或者關(guān)。如果按一下某一盞燈的開(kāi)關(guān)，那么這盞燈的狀態(tài)將發(fā)生改變。如果原來(lái)是開(kāi)，將變成關(guān)。如果原來(lái)是關(guān)，將變成開(kāi)。

在剛開(kāi)始的時(shí)候，所有的燈都是關(guān)的。小明每次可以進(jìn)行如下的操作：

指定兩個(gè)數(shù)，a,t（a?為實(shí)數(shù)，t?為正整數(shù)）。將編號(hào)為 ?a?,?2×a?,?3×a?,…,?t×a??的燈的開(kāi)關(guān)各按一次。其中??k??表示實(shí)數(shù)?k?的整數(shù)部分。

在小明進(jìn)行了?n?次操作后，小明突然發(fā)現(xiàn)，這個(gè)時(shí)候只有一盞燈是開(kāi)的，小明很想知道這盞燈的編號(hào)，可是這盞燈離小明太遠(yuǎn)了，小明看不清編號(hào)是多少。

幸好，小明還記得之前的?n?次操作。于是小明找到了你，你能幫他計(jì)算出這盞開(kāi)著的燈的編號(hào)嗎？

輸入格式

第一行一個(gè)正整數(shù)?n，表示?n?次操作。

接下來(lái)有?n?行，每行兩個(gè)數(shù)，ai?,ti?。其中?ai??是實(shí)數(shù)，小數(shù)點(diǎn)后一定有?6?位，ti??是正整數(shù)。

輸出格式

僅一個(gè)正整數(shù)，那盞開(kāi)著的燈的編號(hào)。

輸入輸出樣例

輸入 #1復(fù)制

3
1.618034 13
2.618034 7
1.000000 21

輸出 #1復(fù)制

20

說(shuō)明/提示

記 T=i=1∑n?ti?=t1?+t2?+t3?+?+tn?。

• 對(duì)于?30%?的數(shù)據(jù)，滿足 T≤1000；
• 對(duì)于?80%?的數(shù)據(jù)，滿足 T≤200000；
• 對(duì)于?100%?的數(shù)據(jù)，滿足 T≤2000000；
• 對(duì)于?100%?的數(shù)據(jù)，滿足 n≤5000，1≤ai?<1000，1≤ti?≤T。

數(shù)據(jù)保證，在經(jīng)過(guò)?n?次操作后，有且只有一盞燈是開(kāi)的，不必判錯(cuò)。而且對(duì)于所有的?i?來(lái)說(shuō)，ti?×ai??的最大值不超過(guò)?2000000。

n=int(input())
arr=[0 for i in range(2000000)] 
'''
開(kāi)線段樹(shù) 關(guān)燈狀態(tài)為0，開(kāi)燈為1，因?yàn)轭}目說(shuō)了最后只有一盞燈亮，那么
就找到那一盞燈的編號(hào)
'''
for i in range(n):a,t=map(float,input().split())for j in range(1,int(t)+1):#原來(lái)亮現(xiàn)在暗if arr[int(j*a)]==0:arr[int(j*a)]=1#原來(lái)暗現(xiàn)在亮elif arr[int(j*a)]==1:arr[int(j*a)]=0
print(arr.index(1))