1 solutions

  • 0
    @ 2022-11-27 20:56:18

        对任意一个数,如果需要满足余数SiS_{i} = AiA_{i} modmod MM,满足每个SiS_{i}相等,我们可以枚举大于2的数来依次去除每一个数,看他们的余数是否相等,但00<=AiA_{i}<=10910^9,对于大数据依次枚举不符合时间要求。
       若存在一个数MM,满足AiA_{i} modmod MM == Ai+1A_{i+1} modmod MM同时它们满足 |AiA_{i}-Ai1A_{i-1}|可以被M整除
      
      例如数字11和数字55,有数字22,它们的余数是11,而它们相减为44能被22整除。
      而这个数可以整除所有的**|AiA_{i}-Ai1A_{i-1}|,问题便转为求各个|AiA_{i}-Ai1A_{i-1}|之间的一个约数,我们可以用gcd来求得这个是否存在这个数。   
      让 ansans=gcd(|A1A_{1}-A2A_{2}|,|A3A_{3}-A2A_{2}|,...|AiA_{i}-Ai1A_{i-1}|)
      
      如果ansans=1,即不存在这个数MM,反之存在数MM可以整除所有的
    |AiA_{i}-Ai1A_{i-1}|**,即所有数经过MODMOD MM后相等.

      辗转相除法:

    int gcd(int a,int b) {
        int r;
        while(b>0) {
            r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
    

      比如现在要求32323636的最大公约数:
       3636 / 2626 = 11...66 (此行除数26作下一行的被除数,余数作为除数)
       2626 / 66 = 44...22 (此行同理)
       66 / 22 = 00 (此处余数为零,意味着最大公约数就是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