【codeforces】#206 C

考虑a[]都>=k的情况 根据抽屉原理 k一定是一个答案
枚举所有>k的答案
对于一个t(>k) 在每个[a[i]-k,a[i]]中
最多只有一个倍数
处理处c[i]表示i这个数被几个区间包含
在check一个t的时候 枚举它的所有倍数
把他们的c值加起来 如果=n 就合法
输出最大的合法的t即可

对于有a[]小于k的情况 最小的a就是答案 显然易证可知可得

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

int c[1000005], n, k, mi;

int main()
{
  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);
  scanf("%d%d", &n, &k);
  int mi = 0x7fffffff;
  for (int i = 0; i < n; ++i)
  {
    int t;
    scanf("%d", &t);
    mi = min(mi, t);
    ++c[max(t - k, 1)];
    --c[t + 1];
  }
  if (mi <= k)
  {
        printf("%d", mi);
        return 0;
    }
  for (int i = 1; i <= 1000000; ++i) c[i] += c[i - 1];
  int ans = k;
  for (int i = k + 1; i <= 1000000; ++i)
  {
    int tot = 0;
    for (int j = i; j <= 1000000; j += i) tot += c[j];
    if (tot == n) ans = i;
  }
  printf("%d", ans);
  //fclose(stdin);fclose(stdout);    
}

全国互虐 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);
}

BZOJ 2790: [Poi2012]Distance

先用线性筛法预处理出1~100w所有数的质因数次数和f[]
枚举gcd 对于一个gcd G 枚举i*G这些数
维护一个最小和次小值 如对于一个数k 它的权值就是f[k/G]
找出最小和次小的 用f[min] + f[i]更新所有i*G这些数的ans
最后输出即可

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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 = 1000005;
const ll mxn = 1000000;

struct line
{
  ll to, next;
}li[maxn * 2];

ll p[maxn], n, m, a[maxn], be[maxn], ans[maxn][2], cnt[maxn], l, b[maxn];

void makeline(ll fr, ll to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

bool check(ll s1, ll s2, ll g)
{
  if (!s1) return true;
  return cnt[a[s1] / g] > cnt[a[s2] / g] || (cnt[a[s1] / g] == cnt[a[s2] / g] && s1 > s2);
}

int main()
{
  scanf("%lld", &n);
  for (ll i = 1; i <= n; ++i)
  {
    scanf("%lld", &a[i]);
    makeline(a[i], i);
  }
  cnt[1] = 0;
  for (ll i = 2; i < maxn; ++i)
  {
    if (!b[i])
    {
      p[m++] = i;
      cnt[i] = 1;
    }
    for (ll j = 0; j < m && p[j] * i < maxn; ++j)
    {
      b[p[j] * i] = 1;
      cnt[p[j] * i] = cnt[i] + 1;
      if (i % p[j] == 0) break;
    }
  }

  for (ll i = 1; i <= mxn; ++i)
  {
    ll mi1 = 0, mi2 = 0;
    for (ll j = i; j <= mxn; j += i)
      for (ll k = be[j]; k; k = li[k].next)
      {
        ll to = li[k].to;
        if (check(mi1, to, i))
          mi2 = mi1, mi1 = to;
        else if (check(mi2, to, i)) mi2 = to;
      }
    if (!mi2) continue;
    for (ll j = i; j <= mxn; j += i)
      for (ll k = be[j]; k; k = li[k].next)
      {
        ll to = li[k].to;
        if (to == mi1)
        {
          ll k = cnt[a[mi2] / i] + cnt[a[to] / i];
          if (ans[to][0] == 0 || (ans[to][1] > k || (ans[to][1] == k && ans[to][0] > mi2)))
          {
            ans[to][0] = mi2;
            ans[to][1] = k;
          }
        }
        else
        {
          ll k = cnt[a[mi1] / i] + cnt[a[to] / i];
          if (ans[to][0] == 0 || (ans[to][1] > k || (ans[to][1] == k && ans[to][0] > mi1)))
          {
            ans[to][0] = mi1;
            ans[to][1] = k;
          }
        }
      }
  }
  for (ll i = 1; i <= n; ++i) printf("%lld\n", ans[i][0]);
}

全国互虐 TEST 6.2【数学难题】

这题= =
赤裸裸的把5题数论拼在一起就变成了数论难题。。
其实这些题也是有一些难点的0 0

直接exgcd即可

显然p-1是一个解 其他的解一定是它的因数(可以证明
于是每次sqrt枚举即可

各种乱推后可以得出答案是
sum(phi(k) * (n / k) * (m / k))
预处理phi前缀和 然后用分段函数的处理方法处理即可

sum(n/i)=sum(f(i))
f(i)表示i的因数个数
证明就是 对于一个i n/i就表示它是几个数的因数 所以一样
f可以用线性筛法预处理
弄出前缀和即可

把b倒序fft即可

BZOJ 3181: [Coci2012]BROJ

因为如果ans > 10^9就输出0
那么可以分情况考虑
如果质数P<100 那么可以先二分ans 然后求出<=mid的 最小质因数为P的个数 也就是求<=mid/P 最小质因数>=P的个数 = mid/P – 最小质因数100
如果它>sqrt(10^9)并且n>1那么必为0 否则输出P
对于剩下的情况 只要枚举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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#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 = 50005;

ll n, P, p[maxn], b[maxn], m;

ll dfs(ll be, ll n, ll tot, ll k)
{
  ll ans = n / tot * k;
  for (ll i = be; i < m && p[i] != P; ++i)
  {
    if (p[i] * tot > n) break;
    ans += dfs(i + 1, n, tot * p[i], k * -1);
  }
  return ans;
}

ll check(ll mid)
{
  return dfs(0, mid / P, 1, 1);
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld%lld", &n, &P);
  for (ll i = 2; i < maxn; ++i)
  {
    if (!b[i]) p[m++] = i;
    for (ll j = 0; j < m && p[j] * i < maxn; ++j)
    {
      b[p[j] * i] = 1;
      if (i % p[j] == 0) break;
    }
  }
  check(300);
  if (P < 100)
  {
    ll l = 0, r = 1000000005;
    while (l + 1 < r)
    {
      ll mid = (l + r) / 2;
      if (check(mid) < n) l = mid;
      else r = mid;
    }
    if (r > 1000000000) printf("0");
    else printf("%lld", r);
  }
  else
  {
    if (P * P > 1000000000)
    {
      if (n == 1) printf("%lld", P);
      else printf("0");
      return 0;
    }
    ll cnt = 0;
    for (ll i = 1; i <= 1000000000 / P; ++i)
    {
      for (ll j = 0; p[j] != P; ++j)
        if (i % p[j] == 0)
        {
          --cnt;
          break;
        }
      ++cnt;
      if (cnt >= n)
      {
        printf("%lld", i * P);
        return 0;
      }
    }
    printf("0");
  }
  fclose(stdin);fclose(stdout);
}