2020ccpc-Weihai威海-D-ABC_Conjecture

2022-10-04

题意

Given a positive integer c, determine if there exists positive integers a, b, such that a + b = c and rad(abc) < c.

where

is the product of all distinct prime divisors of n.

数据范围

解析

• c=1

输出no

• c的质因子的幂均为1,

输出no

• 否则，c的质因子中存在一个幂大于等于2的，输出yes

以上，先筛掉的之内的质因子p，如果有输出yes; 否则， k中k只能为1，这样判断一下是不是素数即可。

code

1#include <bits/stdc++.h>
2#define LL long long
3const int N = 1e6 + 20;
4
5LL prime[N];
6bool bo[N];
7int pcnt;
8
9namespace MillerRabin {
10long long Mul(long long a, long long b, long long mo) {
11    long long tmp = a * b - (long long)((long double)a / mo * b + 1e-8) * mo;
12    return (tmp % mo + mo) % mo;
13}
14
15long long Pow(long long a, long long b, long long mo) {
16    long long res = 1;
17    for (; b; b >>= 1, a = Mul(a, a, mo))
18        if (b & 1)
19            res = Mul(res, a, mo);
20    return res;
21}
22
23bool IsPrime(long long n) {
24    if (n == 2)
25        return 1;
26    if (n < 2 || !(n & 1))
27        return 0;
28    static const auto tester = {2, 3, 5, 7, 11, 13, 17, 19, 23};
29    long long x = n - 1;
30    int t = 0;
31    for (; !(x & 1); x >>= 1)
32        ++t;
33    for (int p : tester) {
34        long long a = p % (n - 1) + 1, res = Pow(a % n, x, n), last = res;
35        for (int j = 1; j <= t; ++j) {
36            res = Mul(res, res, n);
37            if (res == 1 && last != 1 && last != n - 1)
38                return 0;
39            last = res;
40        }
41        if (res != 1)
42            return 0;
43    }
44    return 1;
45}
46} // namespace MillerRabin
47
48namespace PollardRho {
49using namespace MillerRabin;
50unsigned long long seed;
51
52long long Rand(long long mo) { return (seed += 4179340454199820289ll) % mo; }
53
54long long F(long long x, long long c, long long mo) {
55    return (Mul(x, x, mo) + c) % mo;
56}
57
58long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
59
60long long Get(long long c, long long n) {
61    long long x = Rand(n), y = F(x, c, n), p = n;
62    for (; x != y && (p == n || p == 1);
63         x = F(x, c, n), y = F(F(y, c, n), c, n))
64        p = x > y ? gcd(n, x - y) : gcd(n, y - x);
65    return p;
66}
67
68void Divide(long long n, long long p[]) {
69    if (n < 2)
70        return;
71    if (IsPrime(n)) {
72        p[++*p] = n;
73        return;
74    }
75    for (;;) {
76        long long tmp = Get(Rand(n - 1) + 1, n);
77        if (tmp != 1 && tmp != n) {
78            Divide(tmp, p);
79            Divide(n / tmp, p);
80            return;
81        }
82    }
83}
84} // namespace PollardRho
85void makePrime() {
86    for (int i = 2; i < N; ++i) {
87        if (!bo[i]) {
88            prime[++pcnt] = i;
89        }
90        for (int j = 1; j <= pcnt && i * prime[j] < N; ++j) {
91            bo[i * prime[j]] = true;
92            if (i % prime[j]) {
93                break;
94            }
95        }
96    }
97}
98
99int main() {
100    makePrime();
101    int T;
102    std::cin >> T;
103    while (T--) {
104        LL c;
105        std::cin >> c;
106        if (c == 1) {
107            std::cout << "no\n";
108        } else {
109            bool flag = false;
110            for (int i = 1; i <= pcnt; ++i) {
111                int cnt = 0;
112                while (c % prime[i] == 0) {
113                    ++cnt;
114                    c /= prime[i];
115                }
116                if (cnt > 1) {
117                    flag = true;
118                    break;
119                }
120            }
121            if (flag) {
122                std::cout << "yes\n";
123            } else {
124                long long p = sqrt(c);
125                if (p * p == c && MillerRabin::IsPrime(p)) {
126                    std::cout << "yes\n";
127                } else {
128                    std::cout << "no\n";
129                }
130            }
131        }
132    }
133    return 0;
134}