http://codeforces.com/problemset/problem/338/D

由于gcd(i,j)为i的因子,所以拿样例1来说,5,2,1均为行号的因子,所以行号至少是lcm(5,2)=10的倍数。
推而广之,行号至少是的倍数。

再看列号。
由于gcd(i,j)同时又为j的因子,设序列最左边的数的列号为j,则有

所以有

解此同余方程组即得j

最后判断下j+k-1是否<=m

陷阱:

  1. 求lcm需中途判断是否会超long long;
  2. 求出j后还要验证下能否还原出a数组,如果还原不了,由于这一行的数是周期性的,所以后面的j也不能满足,故输出NO
/*30ms,200KB*/

const int mx = 10005;

ll B[mx], M[mx];

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

void exgcd(ll a, ll b, ll& d, ll& x, ll& y)
{
    if (!b) d = a, x = 1LL, y = 0LL;
    else exgcd(b, a % b, d, y, x), y -= x * (a / b);
}

ll inv(ll a, ll m)
{
    ll d, x, y;
    exgcd(a, m, d, x, y);
    return d == 1LL ? (x + m) % m : -1LL;
}

p2 solve_linear_congruence(int n) /// 返回x\equiv b(mod m)中的(b,m)
{
    int i;
    ll x = 0, m = 1, b, d, t;
    For(i, n)
    {
        b = B[i] - x, d = gcd(M[i], m);
        if (b % d) return MP(0, -1); /// 无解
     t = b / d * inv(m / d, M[i] / d) % (M[i] / d);
        x += m * t;
        m *= M[i] / d;
    }
    ll tmp = (x % m + m) % m;
    if (tmp == 0LL) tmp = m;
    return MP(tmp, m);
}

ll n, m, len;

bool ok()
{
    ll i, raw = 1LL;
    For(i, len)
    {
        raw = lcm(raw, M[i]);
        if (raw > n) return false; /// 中途可能超long long,要提前判断。。
 }
    For(i, len) B[i] = -i;
    ll tmp = solve_linear_congruence(len).first;
    if (tmp + len - 1 > m) return false;
    For(i, len) if (gcd(raw, i + tmp) != M[i]) return false; /// 判断解是否可行,否则WA10
 return true;
}

int main()
{
    int i;
    SLLL(n, m, len);
    SA(M, i, len);
    puts(ok() ? "YES" : "NO");
    return 0;
}

Comments

comments powered by Disqus