当前位置: 首页 > news >正文

用deepseek写的一个求原根的程序

include

include

include

include

include

using namespace std;

// 快速幂算法:计算 (a^b) % mod
long long fast_power(long long a, long long b, long long mod) {
long long result = 1;
a = a % mod;

while (b > 0) {if (b & 1) {result = (result * a) % mod;}a = (a * a) % mod;b = b >> 1;
}
return result;

}

// 判断一个数是否为素数
bool is_prime(long long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;

for (long long i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return false;}
}
return true;

}

// 计算欧拉函数 φ(n)
long long euler_phi(long long n) {
long long result = n;

for (long long p = 2; p * p <= n; ++p) {if (n % p == 0) {while (n % p == 0) {n /= p;}result -= result / p;}
}if (n > 1) {result -= result / n;
}return result;

}

// 获取n的所有质因数
vector get_prime_factors(long long n) {
vector factors;

for (long long p = 2; p * p <= n; ++p) {if (n % p == 0) {factors.push_back(p);while (n % p == 0) {n /= p;}}
}if (n > 1) {factors.push_back(n);
}return factors;

}

// 判断g是否是模n的原根
bool is_primitive_root(long long g, long long n) {
if (gcd(g, n) != 1) {
return false;
}

long long phi_n = euler_phi(n);
vector<long long> prime_factors = get_prime_factors(phi_n);for (long long factor : prime_factors) {if (fast_power(g, phi_n / factor, n) == 1) {return false;}
}return true;

}

// 找到模n的所有原根
vector find_primitive_roots(long long n) {
vector primitive_roots;

// 只有特定的数有原根:1, 2, 4, p^k, 2p^k,其中p是奇素数
if (n == 1) {primitive_roots.push_back(1);return primitive_roots;
}
if (n == 2) {primitive_roots.push_back(1);return primitive_roots;
}
if (n == 4) {primitive_roots.push_back(3);return primitive_roots;
}// 检查n是否是p^k或2p^k的形式
bool has_primitive_root = false;if (is_prime(n)) {has_primitive_root = true;
} else {// 检查是否是p^klong long temp = n;long long p = -1;for (long long i = 2; i * i <= temp; ++i) {if (temp % i == 0) {p = i;while (temp % i == 0) {temp /= i;}break;}}if (temp > 1 && p == -1) {p = temp;temp = 1;}if (temp == 1 && is_prime(p) && p % 2 == 1) {has_primitive_root = true;} else if (n % 2 == 0) {// 检查是否是2p^klong long half_n = n / 2;temp = half_n;p = -1;for (long long i = 2; i * i <= temp; ++i) {if (temp % i == 0) {p = i;while (temp % i == 0) {temp /= i;}break;}}if (temp > 1 && p == -1) {p = temp;temp = 1;}if (temp == 1 && is_prime(p) && p % 2 == 1) {has_primitive_root = true;}}
}if (!has_primitive_root) {return primitive_roots;
}long long phi_n = euler_phi(n);
vector<long long> prime_factors = get_prime_factors(phi_n);// 寻找最小的原根
long long min_primitive_root = -1;
for (long long g = 2; g < n; ++g) {if (gcd(g, n) != 1) {continue;}bool is_root = true;for (long long factor : prime_factors) {if (fast_power(g, phi_n / factor, n) == 1) {is_root = false;break;}}if (is_root) {min_primitive_root = g;break;}
}if (min_primitive_root == -1) {return primitive_roots;
}// 找到所有原根
primitive_roots.push_back(min_primitive_root);// 其他原根是 g^k,其中gcd(k, φ(n)) = 1
for (long long k = 2; k < phi_n; ++k) {if (gcd(k, phi_n) == 1) {primitive_roots.push_back(fast_power(min_primitive_root, k, n));}
}sort(primitive_roots.begin(), primitive_roots.end());return primitive_roots;

}

// 测试函数
int main() {
cout << "求原根的程序" << endl;
cout << "============" << endl;

vector<long long> test_cases = {7, 11, 17, 19, 23, 29, 31};for (long long n : test_cases) {cout << "\n模 " << n << " 的原根:" << endl;vector<long long> primitive_roots = find_primitive_roots(n);if (primitive_roots.empty()) {cout << "  模 " << n << " 没有原根" << endl;} else {cout << "  原根数量: " << primitive_roots.size() << endl;cout << "  原根列表: ";for (size_t i = 0; i < primitive_roots.size(); ++i) {cout << primitive_roots[i];if (i != primitive_roots.size() - 1) {cout << ", ";}}cout << endl;// 验证最小的原根if (!primitive_roots.empty()) {long long g = primitive_roots[0];long long phi_n = euler_phi(n);cout << "  验证最小原根 " << g << ":" << endl;cout << "  ";for (long long i = 1; i <= phi_n; ++i) {cout << fast_power(g, i, n);if (i != phi_n) cout << ", ";}cout << endl;}}
}// 用户输入测试
cout << "\n请输入一个数来求其原根(输入0退出): ";
long long n;
while (cin >> n && n != 0) {vector<long long> primitive_roots = find_primitive_roots(n);if (primitive_roots.empty()) {cout << "模 " << n << " 没有原根" << endl;} else {cout << "模 " << n << " 的原根数量: " << primitive_roots.size() << endl;cout << "原根列表: ";for (size_t i = 0; i < primitive_roots.size(); ++i) {cout << primitive_roots[i];if (i != primitive_roots.size() - 1) {cout << ", ";}}cout << endl;}cout << "\n请输入一个数来求其原根(输入0退出): ";
}return 0;

}

http://www.hskmm.com/?act=detail&tid=36186

相关文章:

  • 操作备忘:在AE中让视频中间部分变慢
  • 记一次精简系统Windows11英文版离线安装中文语言包的过程
  • 阿里巴巴数据库开发手册
  • AI元人文:赋能公共治理、司法与监管的价值权衡新范式
  • 基础的sql练习,全都理解你就是高手了!
  • nginx快速实现平滑版本升级
  • Luogu P11159 【MX-X6-T5】 再生 题解 [ 蓝 ] [ 前缀和 ] [ 组合计数 ]
  • 王浩宇 102500416
  • 程序员修炼之路:从小工到专家 读书笔记 2
  • 程序员修炼之路:从小工到专家 读书笔记 3
  • 中级问题
  • 2025.10.21
  • 解答在同步以太坊事件数据时,如何保证后端服务在 API/RPC 不稳定情况下的可用性
  • 程序员修炼之道:从小工到专家 读书笔记 1
  • 好想好想你
  • 10.21日学习笔记
  • 数据库概述
  • 第1天(简单题 基础语法 数据类型、条件判断 、循环 循环嵌套、位运算, ASCII 码)
  • 24信计2班 17曾向嵩 pytorch读书报告
  • 关于第一次作业的时长统计
  • Go 语言问题解释
  • Keil_v5的用法
  • day 8
  • OI 笑传 #21
  • Day1文本格式化标签
  • 【C语言学习记录】你好世界
  • 1021
  • 24信计2班 17曾向嵩 pytorch66页实验题
  • 解答这些常见的智能合约安全问题,并提供相应的防护措施
  • Day1排版标签,标题与段落