1
import math
2
MX = 1_000_001
3
is_p = [False] * 2 + [True] * (MX - 2)
4
p = []
5
for i in range(2, MX):
6
    if is_p[i]:
7
        p.append(i)
8
        for j in range(i * i, MX, i):
9
            is_p[j] = False
10
def is_prime_large(x):
11
    if x < 2:
12
        return False
13
    if x < MX:
14
        return is_p[x]
15
    limit = int(x ** 0.5)
16
    for prime in p:
17
        if prime > limit:
18
            break
19
        if x % prime == 0:
20
            return False
21
    return True
22
n = int(input())
23
for p1 in p:
24
    if p1 * p1 > n:
25
        break
26
    # p1 作为 p（平方的质数）
27
    if n % (p1 * p1) == 0:
28
        q = n // (p1 * p1)
29
        if is_prime_large(q):
30
            print(p1, q)
31
            break
32
    # p1 作为 q
33
    if n % p1 == 0:
34
        t = n // p1
35
        rt = int(t ** 0.5)
36
        if rt * rt == t and is_prime_large(rt):
37
            print(rt, p1)
38
            break

1
#include <iostream>
2
#include <vector>
3
#include <cmath>
4
#include <algorithm>
5
using namespace std;
6
typedef long long ll;
7
const int MX = 1e6 + 5;
8
bool is_p[MX];
9
vector<int> p;
10
void sieve(){
11
    fill(is_p,is_p + MX,true);
12
    is_p[0] = is_p[1] = false;
13
    for(int i = 2;i < MX;i++){
14
        if(is_p[i]){
15
            p.push_back(i);
16
            for(long long j = 1LL*i*i;j < MX;j+=i){
17
                is_p[j] = false;
18
            }
19
        }
20
    }
21
}
22
bool check_prime(ll x) {
23
    if (x < 2) return false;
24
    if (x < MX) return is_p[x];
25
    for (int p1 : p) {
26
        if (1LL * p1 * p1 > x) break;
27
        if (x % p1 == 0) return false;
28
    }
29
    return true;
30
}
31
int main(){
32
    ios::sync_with_stdio(false);
33
    cin.tie(nullptr);
34
    sieve();
35
    ll n;
36
    cin >> n;
37
    for(int p1 : p){
38
        if(1ll *p1*p1 > n){
39
            break;
40
        }
41
        if(n%(1ll*p1*p1) == 0){
42
            ll q = n / (1ll * p1 * p1);
43
            if(check_prime(q)){
44
                cout << p1 << " "<< q << endl;
45
                return 0;
46
            }
47
        }
48
        if(n%p1 == 0){
49
            ll t = n/p1;
50
            ll rt = sqrt(t);
51
            if(rt * rt == t && check_prime(rt)){
52
                cout << rt << " " << p1 << endl;
53
                return 0;
54
            }
55
        }
56
    }
57
    return 0;
58
}

1
n,k = map(int,input().split())
2
a = list(map(int,input().split()))
3
# while k > 0:
4
#     k -= 1
5
#     b = []
6
#     for i in range(1,len(a)):
7
#         if a[i] not in b:
8
#             b.append(a[i])
9
#         if a[i]+1 not in b:
10
#             b.append(a[i] + 1)
11
#     a = b
12
# print(len(a))
13
a.sort()
14
b = [(a[i], a[i] + k) for i in range(1, n)]
15
b.sort()
16
c = []
17
for l, r in b:
18
    if not c or l > c[-1][1] + 1:
19
        c.append([l, r])
20
    else:
21
        c[-1][1] = max(c[-1][1], r)
22
tot = sum(r - l + 1 for l, r in c)
23
ans = max(0, tot - (k - 1))
24
print(ans)

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5
typedef long long ll;
6
int main() {
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9
    int n, k;
10
    cin >> n >> k;
11
    vector<int> a(n);
12
    for (int i = 0; i < n; i++) {
13
        cin >> a[i];
14
    }
15
    sort(a.begin(), a.end());
16

17
    if (k == 0) {
18
        cout << n << "\n";
19
        return 0;
20
    }
21

22
    if (n == 1) {
23
        cout << 0 << "\n";
24
        return 0;
25
    }
26
    vector<pair<ll, ll>> intervals;
27
    for (int i = 1; i < n; i++) {
28
        intervals.push_back({a[i], a[i] + k});
29
    }
30
    sort(intervals.begin(), intervals.end());
31
    vector<pair<ll, ll>> merged;
32
    for (auto& [l, r] : intervals) {
33
        if (merged.empty() || l > merged.back().second + 1) {
34
            merged.push_back({l, r});
35
        } else {
36
            merged.back().second = max(merged.back().second, r);
37
        }
38
    }
39
    ll total = 0;
40
    for (auto& [l, r] : merged) {
41
        total += r - l + 1;
42
    }
43
    ll ans = max(0LL, total - (k - 1));
44
    cout << ans << "\n";
45

46
    return 0;
47
}

1
n = int(input())
2
a = list(map(int, input().split()))
3

4
# 检查异或和
5
xor_sum = 0
6
for x in a:
7
    xor_sum ^= x
8
if xor_sum != 0:
9
    print(-1)
10
    exit()
11

12
# 计算前缀异或
13
P = [0] * n
14
P[0] = 0
15
for i in range(1, n):
16
    P[i] = P[i-1] ^ a[i]
17

18
# 按位统计
19
ans = 0
20
for b in range(30):
21
    cnt = sum(1 for p in P if (p >> b) & 1)
22
    ans += min(cnt, n - cnt)
23
print(ans)