题解 P1356 【数列的整数性】

弑君 · 2019-01-07 13:21:48 · 题解

这题随机数真的可以A 上代码（人品好可以一遍过）

#include<bits/stdc++.h>
#define N 11100
#define R register
#define il inline
typedef long long ll;
#define f1(a,b,c) for(R ll a=b;a<=c;a++)
using namespace std;
ll n,m,s,a[N];
bool bk;
il void re(ll&x)
{
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
int main()
{
    ll t;re(t);
    while(t--)
    {
        s=bk=false;re(n),re(m);
        f1(i,1,n)
        {
            ll x;re(x);
            if(x%m)a[++s]=x;
        }
        ll j=250;while(j--)
        {
            ll sum=0;
            f1(i,1,s)
            {
                ll p=rand();//随机数A题
                p%2?sum+=a[i]:sum-=a[i];
            }
            if(!(sum%m))
            {
                printf("Divisible\n",bk=true);
                break;
            }
        }
        if(!bk)printf("Not divisible\n");
    }
    return 0;
}