1 solutions
-
0
对任意一个数,如果需要满足余数 = ,满足每个相等,我们可以枚举大于2的数来依次去除每一个数,看他们的余数是否相等,但<=<=,对于大数据依次枚举不符合时间要求。
若存在一个数,满足 ,同时它们满足 |-|可以被M整除。
例如数字和数字,有数字,它们的余数是,而它们相减为能被整除。
而这个数可以整除所有的**|-|,问题便转为求各个|-|之间的一个约数,我们可以用gcd来求得这个是否存在这个数。
让 =gcd(|-|,|-|,...|-|)。
如果=1,即不存在这个数,反之存在数可以整除所有的|-|**,即所有数经过 后相等.辗转相除法:
int gcd(int a,int b) { int r; while(b>0) { r=a%b; a=b; b=r; } return a; }
比如现在要求,的最大公约数:
/ = ... (此行除数26作下一行的被除数,余数作为除数)
/ = ... (此行同理)
/ = (此处余数为零,意味着最大公约数就是2)
反复把一个式子中的除数当作被除数去除余数,直到最后余数等于0。
最大公约数就是最后那个式子的除数,本例就是2。
gcd库函数:#include <algorithm> int gcd(int a,int b) { return __gcd(a,b); }
可以用来求两数的最大公约数。
完整代码如下#include<bits/stdc++.h> const int N =2e5; using namespace std; int a[N]={0}; int gcd(int a,int b) {//辗转相除法 int r; while(b>0) { r=a%b; a=b; b=r; } return a; } int main() { int n,ans=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; ans=abs(a[2]-a[1]); for(int i=3;i<=n;i++) { // ans=__gcd(ans,abs(a[i]-a[i-1]));库函数 ans=gcd(ans,abs(a[i]-a[i-1])); } if(ans==1) cout<<"No"; else cout<<"Yes"; return 0; }
- 1
Information
- ID
- 6634
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 131
- Accepted
- 11
- Uploaded By