题解分享
题解分享简介
等差数列(编程题) - 题解
```
from math import gcd
N = int(input())
A = list(map(int, input().split()))
A.sort()
diff = 0
for i in range(1, N):
diff = gcd(diff, A[i] - A[i - 1])
if not diff:
print(n)
else:
print((A[-1] - A[0]) // diff + 1)
```
查看全文
0
0
0
2
等差数列(编程题) - 题解
```
include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int n,t=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
t=gcd(a[i]-a[1],t);
}
if(!t)
cout<<n;
else
cout<<((a[n]-a[1])/t)+1;
return 0;
}
```
查看全文
0
0
0
2
等差数列(编程题) - 题解
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 10;
int n;
int a[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int d = a[2] - a[1];
if (d == 0)
{
cout << n << endl;
return;
}
for (int i = 3; i <= n; i++)
d = __gcd(d, a[i] - a[i - 1]); // 求所有差的最大公约数
cout << (a[n] - a[1]) / d + 1 << endl; // (an-a1)/d + 1求等差数列项数
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
```
查看全文
0
0
0
1
等差数列(编程题) - 题解
```
from math import *
n = int(input())
a = list(map(int,input().split()))
a.sort()
d = 0
for i in range(1,n):
d = gcd(d,a[i]-a[i-1])
if d == 0:
print(n)
else:print((a[-1]-a[0])//d+1)
```
0
0
0
1
等差数列(编程题) - 题解
我认为是经验和找规律才可以思考到 [公差为(arr[i] - arr[i + 1])的最小公约数], 如果不是刚刚学习了某知识, 在考场上怎么才可以想到这里啊qwq😕
```C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int fxxk(int a, int b) {
return b == 0 ? a : fxxk(b, a % b);
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i];
sort(arr.begin(), arr.end());
// 等差数列
// 公差为(arr[i] - arr[i + 1])的最小公约数
// 如果有 2 6 4 8 为可能的公差, 那么要选择他们的最小公倍数 即 2
ll res = 1;
int fk = arr[1] - arr[0];
for (int i = 2; i < n; ++i) {
fk = min(fk, fxxk(arr[i - 1] - arr[i - 2], arr[i] - arr[i - 1]));
}
// 现在已知 首项 arr[0] 与 末项 arr[n - 1] 和公差 fk
// 由 a1 + (n - 1) * d = an
// 即 arr[0] + (len - 1) * d = arr[n - 1] # 注: 此处的 n 与 len 的意义不同,
// 一个是 arr数组长度n 是 不连续的数列,
// 另一个 len 是 完整的数列的长度
// 则 len = (arr[n - 1] - arr[0]) / d + 1
if (n == 2)
cout << 2 << '\n';
else
cout << (arr[n - 1] - arr[0]) / fk + 1 << '\n';
return 0;
}
```
查看全文
0
0
0
0
