(2485) 가로수

https://www.acmicpc.net/problem/2485

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 4번째

 

 

 

n-1개 간격 전부의 최대공약수를 구하면 된다. 증명은 생략하지만 gcd(a,b,c)=gcd(gcd(a,b),c)이므로 두개씩 순차적으로 구하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b){
  pair<int,int> p= {a,b};
  
  while(p.second)  p= {p.second, p.first%p.second};
  
  return p.first;
}

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  int res= v[1]-v[0];
  
  for(int i=2;i<n;i++)  res= gcd(res, v[i]-v[i-1]);
  
  cout << (v[n-1]-v[0])/res+1-n;
  
  return 0;
}