Oct 4, 2022 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.whererad(𝑛)=∏𝑝∣𝑛𝑝∈Prime𝑝is the product of all distinct prime divisors of n.数据范围1⩽𝑇⩽10,1⩽𝑐⩽1018解析•c=1输出no•c的质因子的幂均为1, 𝜇(𝑐)=−1输出no•否则，c的质因子中存在一个幂大于等于2的，输出yes𝑐=𝑝2𝑘,𝑎=𝑝𝑘,𝑏=𝑝(𝑝−1)𝑘,𝑎+𝑏=𝑐𝑎𝑏𝑐=𝑝4(𝑝−1)𝑘3rad(𝑎𝑏𝑐)=rad(𝑝4(𝑝−1)𝑘3)=rad(𝑝(𝑝−1)𝑘)≤(𝑝−1)𝑘<𝑐以上，先筛掉𝑐的106之内的质因子p，如果有输出yes; 否则，𝑐=𝑝2 k中k只能为1，这样判断一下√𝑐是不是素数即可。code1#include <bits/stdc++.h>2#define LL long long3const int N = 1e6 + 20;45LL prime[N];6bool bo[N];7int pcnt;89namespace 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}1415long 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}2223bool 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 MillerRabin4748namespace PollardRho {49using namespace MillerRabin;50unsigned long long seed;5152long long Rand(long long mo) { return (seed +=4179340454199820289ll) % mo; }5354long long F(long long x, long long c, long long mo) {55 return (Mul(x, x, mo) + c) % mo;56}5758long long gcd(long long a, long long b) { return b ? gcd(b, a %b) : a; }5960long 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}6768void 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 PollardRho85void 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}9899int 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}