오일러1044

#1044 꽃 축제 : 오일러OJ (euleroj.io)

 

브루트 포스 알고리즘

 

 

#나는 일렬로 길게 울타리를 따라서 S(7≤S≤10,000)개의 빈 슬롯(slot)에 

#꽃을 심을 생각이다

#연속적으로 3칸의 간격으로 장미를 심고

# 7칸의 간격으로 베고니아를 심고

# 4칸의 간격으로 데이지를 심을 것이다

#각각의 꽃마다 처음 시작하는 슬롯에서부터 꽃을 심기 시작해서

# 일정한 간격으로 빈 슬롯이 존재한다면 그 슬롯에 꽃을 심어나간다

# 오일러는 N(1≤N≤100)개의 꽃을 심을 계획

# 각각의 꽃들은 A(1≤A≤S)의 슬롯부터 꽃을 심기 시작

#B(1≤B≤S)의 간격으로 꽃을 심어 나갈 것

#첫째 줄에는 두 개의 정수 S와 N이 주어진다. 

#둘째 줄부터는 각각의 i번째 꽃들에 대한 정보가 N줄에 걸쳐서 주어진다

#따라서 i번째 꽃들에 대한 정보는 i + 1번째 줄에 주어진다.

#각각의 꽃들에 대한 정보는 두 개의 정수 A_i와 B_i로 주어진다

slot=[]

flower=[]#홀수 인덱스는 start, 짝수는 간격

cnt=0

s,n=input().split()

s=int(s)

n=int(n)

#빈 슬롯애 일단 0으로 초기화

for i in range(0,s):

    slot.append(0)

for i in range(0,n*2):

    flower.append(0)

for i in range(0,n*2,2):

    flower[i],flower[i+1]=map(int , input().split())

for i in range(0,n*2,2):

    start=flower[i]

    plus=flower[i+1]

    for j in range(start,s,plus):

        if slot[j]==0:

            slot[j]=1

        

for i in range(0,len(slot)):

    if slot[i]==0:

        cnt+=1

print(cnt)