526互联

Add Modulo 10(数论,思维,数学,规律)

发布时间 2023-06-20 11:52:55作者: o-Sakurajimamai-o

思路：找规律

情况一：尾数为$5$或$0$

为$5$时进行一次操作变成$0$的情况。

而尾数是 0 时操作无意义，所有数必须相等。

情况二：尾数为 1,3,7,9

可进行一次操作变成情况三。

情况三：尾数为 2,4,6,8

我们通过找规律发现：

2⇒4⇒8⇒16⇒22
4⇒8⇒16⇒22⇒24
6⇒12⇒14⇒18⇒26
8⇒16⇒22⇒24⇒28

每个数可以转换为它自己 +20 的数，我们可以让每个数加足够多的 20，所以不妨  mod20 再进行比较。

而我们把尾数统一（比如都变成 2）之后，2 和 12 再也不能变成相同的了，所以这时全相等就相当于符合要求。

可以开$set$来进行判断:

//Add Modulo 10:https://www.luogu.com.cn/problem/CF1714E
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int res,n,m,k,t;
set<int>s;
int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        s.clear();
        for(int i=0;i<n;i++){
            cin>>k;
            if(k%2) k=k+k%10;
            if(k%10) k=k%20;
            s.insert(k);
        }
        set<int>p;
        for(auto i:s)
        {
            if(i%10!=0){
                if(i%10==4) i=(i+18)%20;
                else if(i%10==6) i=(i+6)%20;
                else if(i%10==8) i=(i+14)%20;
            }
            p.insert(i);
        }
        if(p.size()==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}