全国互虐 TEST 6.7【ZL密码锁】

数论啊T_T
可以证明gcd(a[x], a[y]) = a[gcd(x, y)]
每次直接算出s和t
(这题如果数据强一点的话这样是不能过的= = 但是出题人说最大的gcd都不大
然后现在就是算ax^2 + bx + c = 0 (mod p)
可以配方成y^2 mod p = d
如果d % p == 0那就只有一个解:y=0
否则 就是求二次剩余
如果d^((p – 1) / 2) = 1 (mod p)则有解 且是两个
否则无解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

ll a[maxn], c[20], m, n, s, t, d, y, x, p, r;

ll gcd(ll a, ll b)
{
  return (!b) ? a : gcd(b, a % b);
}

ll power(ll a, ll n)
{
  ll ans = 1;
  for (; n; n >>= 1)
  {
    if (n & 1) ans = (ans * a) % p;
    a = (a * a) % p;
  }
  return (ans % p + p) % p;
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld", &m);
  for (ll i = m; i >= 0; --i) scanf("%lld", &c[i]);
  ll T;
  scanf("%lld", &T);
  while (T--)
  {
    scanf("%lld%lld%lld%lld", &x, &y, &r, &p);
    s = 0, t = 0;
    ll g = gcd(x, y);
    for (ll i = 1; i <= g; ++i)
    {
      ll ls = s, lt = t;
      s = t = 0;
      for (ll j = m; j >= 0; --j)
        s = (s * ls + c[j]) % x,
        t = (t * lt + c[j]) % y;
    }
    ll a = r, b = s, c = t;
    ll d = (b * b - 4 * a * c) % p;
    if (d % p == 0) printf("1\n");
    else
    {
      if (power(d, (p - 1) / 2) == 1) printf("2\n");
      else printf("0\n");
    }
  }
  fclose(stdin);fclose(stdout);
}

发表评论