AcWing 1246. 等差数列(辗转相除法求最大公约数)
原题链接
中等
作者:
逸误
,
2024-02-13 22:10:46
,
所有人可见
,
阅读 36
//转化为最大公约数问题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int n;
int a[N];
int res;
int gcd(int a,int b)//注意,0和任何数求最大公约数就是那个数本身(0属于零元)
{
return b?gcd(b,a%b):a;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int xiuzheng=a[0];
for(int i=0;i<n;i++)
a[i]-=xiuzheng;
res=a[1];
for(int i=2;i<n;i++)
res=gcd(res,a[i]);
//求得的res是这些数字的最大公约数
int answer;
if(res)//最大公约数是0的特殊情况不要忽略!(常数数列)
answer=a[n-1]/res+1;
else
answer=n;
cout<<answer<<endl;
return 0;
}