two pointers 双指针
给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使得它们的和恰好为M，输出所有满足条件的方案。例如给定序列{1,2,3,4,5,6}和正整数M = 8，就存在2+6=8和3+5=8成立。
容易想到：使用二重循环枚举序列中的整数a和b，判断它们的和是否为M，如果是，输出方案，如果不是，则继续枚举。
代码如下，时间复杂度为O（n^2）。
for(int i=0;i<n;i++){
for(int j=i+1;i<n;i++)
{
if(a[i]+a[j]==M){
printf("%d %d\n",a[i],a[j]);
}
}
}优化算法如下：该算法的时间复杂度为O（n）。
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
int main(){
int n,k;
int cnt = 0;
cin>>n>>k;
int i = 0,j = n-1;
for(int i=0;i<n;i++) cin>>a[i];
while(i<j){
if(a[i]+a[j]==k){
cnt++;
i++;
j--;
}else if(a[i]+a[j]<k){
i++;
}else {
j--;
}
}
cout<<cnt;
return 0;
}#include <cstdio>
#include <iostream>
using namespace std;
// 定义常量 N，用于确定数组的最大长度
const int N = 1e5 + 10;
// 定义三个数组 a、b、c，分别用于存储两个待合并的有序数组和合并后的有序数组
int a[N], b[N], c[N];
// 合并函数，将两个有序数组合并为一个有序数组
int merge(int a[], int b[], int c[], int n, int m) {
// i 指向数组 a 的起始位置，j 指向数组 b 的起始位置，index 指向数组 c 的起始位置
int i = 0, j = 0, index = 0;
// 当数组 a 和数组 b 都还有元素未处理时
while (i < n && j < m) {
// 如果 a[i] 小于等于 b[j]，将 a[i] 放入数组 c 中，并将 i 和 index 指针后移
if (a[i] <= b[j]) c[index++] = a[i++];
// 否则将 b[j] 放入数组 c 中，并将 j 和 index 指针后移
else c[index++] = b[j++];
}
// 如果数组 a 还有剩余元素，将其依次放入数组 c 中
while (i < n) c[index++] = a[i++];
// 如果数组 b 还有剩余元素，将其依次放入数组 c 中
while (j < m) c[index++] = b[j++];
// 返回合并后数组 c 的长度
return index;
}
int main() {
int n, m;
// 读取数组 a 的长度 n 和数组 b 的长度 m
scanf("%d%d",&n,&m);
// 读取数组 a 的 n 个元素
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
// 读取数组 b 的 m 个元素
for (int i = 0; i < m; i++) scanf("%d",&b[i]);
// 调用 merge 函数合并数组 a 和数组 b 到数组 c 中，并获取合并后数组 c 的长度
int res = merge(a, b, c, n, m);
// 输出合并后数组 c 的元素
for (int i = 0; i < res; i++) {
printf("%d", c[i]);
// 除了最后一个元素，每个元素后面输出一个空格
if (i < res - 1) cout << " ";
}
return 0;
}递归写法
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1010;
int a[maxn];
//将数组A的[L1,R1]与[L2,r2]区间合并为有序区间(此处L2即为r1+1)
void merge(int a[], int l1, int r1, int l2, int r2) {
int i = l1, j = l2; //i指向a[l1],j指向a[l2]
int temp[maxn], index = 0; //temp临时存放合并后的数组，index为其下标
while (i <= r1 && j <= r2) {
if (a[i] <= a[j]) { //如果a[i]<=a[j]
temp[index++] = a[i++]; //将a[i]加入序列temp
} else {
temp[index++] = a[j++];
}
}
while (i <= r1) temp[index++] = a[i++];
while (j <= r2) temp[index++] = a[j++];
for (i = 0; i < index; i++) {
a[l1 + i] = temp[i]; //将合并后的序列赋值给数组a
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(int a[], int left, int right) {
if (left < right) { //只要left小于right
int mid = (left + right) / 2; //取[left,right]的中点
mergeSort(a, left, mid); //递归，将左子区间[left,mid]归并排序
mergeSort(a, mid + 1, right); //递归，将右子区间[mid+1,right]归并排序
merge(a, left, mid, mid + 1, right); //将左子区间和右子区间合并
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 调用归并排序函数对数组进行排序
mergeSort(a, 0, n - 1);
// 输出排序后的数组
for (int i = 0; i < n; i++) {
cout << a[i];
if (i < n - 1) cout << " ";
}
return 0;
} 非递归写法
/*1. 外层循环 for(int step = 2; step/2 <= n; step *= 2)
step 的含义：step 表示当前每组元素的个数。在归并排序的非递归实现中，我们从最小的有序子数组开始合并，初始时每组有 2 个元素（即 step = 2），然后每次将 step 乘以 2，逐渐扩大每组的元素个数。
循环条件 step/2 <= n：当 step/2 大于数组的长度 n 时，说明已经完成了所有的合并操作，因为此时分组已经包含了整个数组，所以循环结束。
step *= 2：每次循环结束后，将 step 乘以 2，这样就可以将相邻的两个有序子数组合并成一个更大的有序数组。
2. 内层循环 for(int i = 1; i <= n; i += step)
i 的含义：i 表示当前组的起始位置。每次循环将 i 增加 step，这样就可以依次处理数组中的每一组元素。
循环条件 i <= n：确保 i 不会超出数组的范围。
3. int mid = i + step/2 - 1
mid 的含义：mid 表示当前组中左子区间的最后一个元素的下标。因为左子区间的元素个数为 step/2，所以 mid 的值为 i + step/2 - 1。
4. if(mid + 1 <= n)
判断右子区间是否存在元素：如果 mid + 1 大于数组的长度 n，说明右子区间不存在元素，不需要进行合并操作；否则，需要将左子区间 [i, mid] 和右子区间 [mid + 1, min(i + step - 1, n)] 进行合并。
5. merge(a, i, mid, mid + 1, min(i + step - 1, n))
调用 merge 函数进行合并：merge 函数的作用是将两个有序子数组合并成一个更大的有序数组。这里的左子区间为 [i, mid]，右子区间为 [mid + 1, min(i + step - 1, n)]。使用 min(i + step - 1, n) 是为了防止右子区间的下标超出数组的范围。
注意事项
代码中数组的下标是从 1 开始的，而在 C++ 中数组的下标通常是从 0 开始的。如果要在实际代码中使用，需要根据具体情况进行调整。
代码中使用了变量 n，但在提供的代码片段中并没有对 n 进行定义，在实际使用时需要确保 n 是数组的长度*/
void mergeSort(int a[]){
// step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取
for(int step = 2; step/2 <= n; step *= 2){
// 每step个元素一组，组内前step/2和后step/2个元素进行合并
for(int i = 1; i <= n; i += step){ // 对每一组
int mid = i + step/2 - 1; // 左子区间元素个数为step/2
if(mid + 1 <= n){ // 右子区间存在元素则合并
// 左子区间为[i, mid], 右子区间为[mid + 1, min(i + step - 1, n)]
merge(a, i, mid, mid + 1, min(i + step - 1, n));
}
}
}
}快速排序的交换方式：
//对区间[left,right]进行划分
int partition(int a[],int left,int right){
int temp = a[left];//将a[left]存放至临时变量temp
while(left<right){//只要left与right
while(left<right&&a[right]>temp) right--;//反复左移right
a[left] = a[right];//将a[right]挪到a[left]
while(left<right&&a[left]<=temp) left++;//反复右移left
a[right] = a[left];//将a[left]挪到a[right]
}
a[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
} 快速排序的递归实现如下：
//快速排序，left 与right初值为序列首尾下标（如1,与n）
void quicksort(int a[],int left,int right){
if(left<right){//当前区间的长度不超过1
//将[left,right]按a[left]一分为二
int pos = partition(a,left,right);
quicksort(a,left,pos-1);//对左子区间递归进行快速排序
quicksort(a,pos+1,right); //对右子区间递归进行快速排序
}
}#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1010;
int a[maxn];
//对区间[left,right]进行划分
int partition(int a[],int left,int right){
int temp = a[left];//将a[left]存放至临时变量temp
while(left<right){//只要left与right不相遇
while(left<right&&a[right]>temp) right--;//反复左移right
a[left] = a[right];//将a[right]挪到a[left]
while(left<right&&a[left]<=temp) left++;//反复右移left
a[right] = a[left];//将a[left]挪到a[right]
}
a[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
}
//快速排序，left 与right初值为序列首尾下标（如1,与n）
void quicksort(int a[],int left,int right){
if(left<right){//当前区间的长度不超过1
//将[left,right]按a[left]一分为二
int pos = partition(a,left,right);
quicksort(a,left,pos-1);//对左子区间递归进行快速排序
quicksort(a,pos+1,right); //对右子区间递归进行快速排序
}
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
quicksort(a,0,n-1);
for(int i=0;i<n;i++){
cout<<a[i];
if(i<n-1) cout<<" ";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int mod = 1e9 + 7;
int leftnump[maxn] = {0}; // 每一位左边（含）p的个数
int main() {
string str;
getline(cin, str);
int len = str.size();
for (int i = 0; i < len; i++) { // 从左到右遍历字符串
if (i > 0) { // 如果不是0号位
leftnump[i] = leftnump[i - 1]; // 继承上一位的结果
}
if (str[i] == 'P') { // 当前为是P
leftnump[i]++; // 令leftnump[i]加1
}
}
int ans = 0, rightnumt = 0; // ans为答案，rightnumt记录右边t的个数
for (int i = len - 1; i >= 0; i--) {
if (str[i] == 'T') {
rightnumt++;
} else if (str[i] == 'A') {
ans = (ans + leftnump[i] * rightnumt) % mod; // 累计乘积
}
}
cout << ans << endl;
return 0;
} #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int a,int b){ //递减排序
return a>b;
}
void to_array(int n,int num[]){//将n的每一位存到num数组中
for(int i=0;i<4;i++){
num[i] = n%10;
n/=10;
}
}
int to_number(int num[]){//将num数组转换为数字
int sum = 0;
for(int i=0;i<4;i++){
sum = sum*10+num[i];
}
return sum;
}
int main(){
int n;cin>>n;
int min,max;
int num[5];
while(1){
to_array(n,num);//将n转换为数组
sort(num,num+4);//对num数组中元素从小到大排序
min = to_number(num);//获取最小值
sort(num,num+4,cmp);//获取最大值
max = to_number(num);
n = max-min;//得到下一个数
printf("%04d - %04d = %04d\n",max,min,n);
if(n==0||n==6174) break;
}
return 0;
}#include <cstdio>
#include <iostream>
using namespace std;
// 定义一个函数 gcd，用于计算两个整数 a 和 b 的最大公约数
// 该函数使用欧几里得算法（辗转相除法）来实现
int gcd(int a, int b) {
// 当 b 为 0 时，a 就是最大公约数，直接返回 a
if (b == 0) return a;
// 若 b 不为 0，则递归调用 gcd 函数，将 b 和 a 除以 b 的余数作为新的参数
// 这是根据欧几里得算法的原理：gcd(a, b) = gcd(b, a % b)
else return gcd(b, a % b);
}
int main() {
int m, n;
// 使用 while 循环和 scanf 函数不断从标准输入读取两个整数 m 和 n
// scanf 函数返回成功匹配并赋值的输入项数量，当输入结束（遇到文件结束符 EOF）时，scanf 返回 EOF
// 所以这里的条件是当 scanf 成功读取两个整数时，循环继续执行
while (scanf("%d%d", &m, &n) != EOF) {
// 调用 gcd 函数计算 m 和 n 的最大公约数
// 并使用 printf 函数将结果输出到标准输出，每个结果占一行
printf("%d\n", gcd(m, n));
}
return 0;
} #include <cstdio>
#include <iostream>
using namespace std;
// 定义函数gcd，用于计算两个整数a和b的最大公约数
// 采用欧几里得算法（辗转相除法），即两个整数的最大公约数等于较小数和两数相除余数的最大公约数
// 当b为0时，a就是最大公约数，返回a
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int main() {
int m, n;
// 从标准输入读取两个整数m和n
// 使用cin输入流，它是C++中用于从标准输入设备（通常是键盘）读取数据的对象
cin >> m >> n;
// 计算并输出m和n的最小公倍数
// 根据最小公倍数的计算方法：两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数
// 先调用gcd函数计算m和n的最大公约数，然后通过公式m/gcd(m,n)*n计算最小公倍数并输出
// 使用cout输出流，它是C++中用于向标准输出设备（通常是显示器）输出数据的对象
cout << m / gcd(m, n) * n;
return 0;
}#include <cstdio> // 包含标准输入输出函数的头文件，如 scanf 和 printf
#include <cstring> // 包含字符串处理函数的头文件，这里主要使用 memset 函数
#include <vector> // 包含 vector 容器相关的头文件，用于存储素数
using namespace std;
const int MAXN = 1000000 + 1; // 定义一个常量，表示数组的最大长度，用于标记每个数是否为素数
bool isPrime[MAXN]; // 定义一个布尔类型的数组，用于标记每个数是否为素数，初始假设所有数都是素数
vector<int> primes; // 定义一个 vector 容器，用于存储筛选出的素数
// 函数功能：使用埃拉托斯特尼筛法筛选出小于等于 n 的所有素数
void getPrimes(int n) {
// 将 isPrime 数组的所有元素初始化为 true，表示所有数都假设为素数
memset(isPrime, true, sizeof(isPrime));
// 从 2 开始遍历到 n
for (int i = 2; i <= n; i++) {
// 如果 isPrime[i] 为 true，说明 i 是素数
if (isPrime[i]) {
// 将素数 i 添加到 primes 容器中
primes.push_back(i);
// 从 i 的 2 倍开始，以 i 为步长，将所有 i 的倍数标记为非素数
for (int j = i + i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
}
int main() {
int n;
// 从标准输入读取一个整数 n，n 表示要筛选小于等于 n 的素数
scanf("%d", &n);
// 调用 getPrimes 函数筛选出小于等于 n 的所有素数
getPrimes(n);
// 遍历 primes 容器，将其中存储的素数依次输出，每个素数占一行
for (int i = 0; i < primes.size(); i++) {
printf("%d\n", primes[i]);
}
return 0;
}#include <cstdio>
#include <iostream>
using namespace std;
// 定义一个常量，表示数组的最大长度，用于标记数是否为素数的数组大小
const int maxn = 1e6 + 10;
// 布尔类型数组，用于标记每个数是否为素数，初始值都设为false（0表示false）
bool p[maxn] = {0};
// 用于存储素数的数组
int prime[maxn];
// 记录素数的数量，初始值为0
int pnum = 0;
// 用于接收用户输入的整数n
int n;
// 函数功能：筛选出小于等于n的所有素数
void findprime() {
// 从2开始遍历到n，因为1不是素数
for (int i = 2; i <= n; i++) {
// 如果p[i]为false，说明当前数i还未被标记为合数，即i是素数
if (p[i] == false) {
// 将素数i存入prime数组中，并更新素数数量pnum
prime[pnum++] = i;
// 从i的2倍开始，将i的所有倍数标记为合数（即p[j]设为true）
for (int j = i + i; j < maxn; j += i) {
p[j] = true;
}
}
}
}
int main() {
// 从标准输入读取一个整数n
cin >> n;
// 调用findprime函数筛选小于等于n的素数
findprime();
// 遍历prime数组，输出所有找到的素数
for (int i = 0; i < pnum; i++) {
printf("%d\n", prime[i]);
}
return 0;
}#include <cstdio>
#include <iostream>
using namespace std;
// 定义一个常量，表示数组的最大长度，这里设置为 1e6 + 10，用于存储素数和标记数组
const int maxn = 1e6+10;
// 用于存储素数的数组，下标从 0 开始
int prime[maxn],num = 0;
// 用于标记数组，p[i] 为 true 表示 i 不是素数，为 false 表示 i 可能是素数
bool p[maxn] = {0};
// 函数功能：筛选出前 n 个素数并存储在 prime 数组中
void findprime(int n){
// 从 2 开始遍历到 maxn - 1（因为数组下标从 0 开始，最大到 maxn - 1）
for(int i=2;i<maxn;i++){
// 如果 p[i] 为 false，说明 i 还未被标记为合数，即 i 是素数
if(p[i]==false){
// 将素数 i 存入 prime 数组中，并更新素数的数量 num
prime[num++] = i;
// 如果已经找到了 n 个素数，就退出循环，不需要再继续找了
if(num>=n) break;
// 从 i 的 2 倍开始，将 i 的所有倍数标记为合数（即 p[j] 设为 true）
for(int j=i+i;j<maxn;j+=i) {
p[j] = true;
}
}
}
}
int main(){
int m,n,count = 0;
// 从标准输入读取两个整数 m 和 n，m 表示要输出的素数的起始位置（从 1 开始计数），n 表示结束位置
cin>>m>>n;
// 调用 findprime 函数，筛选出前 n 个素数
findprime(n);
// 遍历从 m 到 n 的素数，并按照规定格式输出
for(int i=m;i<=n;i++){
// prime 数组的下标从 0 开始，所以输出 prime[i - 1]
printf("%d",prime[i-1]);
// 记录已经输出的素数的个数
count++;
// 如果 count 不是 10 的倍数且还未输出到最后一个素数（i < n），则输出一个空格分隔
if(count%10!=0&&i<n) cout<<" ";
// 否则换行
else cout<<"\n";
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
// 从标准输入读取一个整数 n
cin >> n;
// 输出格式：先输出 "n="
printf("%d=", n);
// 如果 n 等于 1，直接输出 "1" 并换行
if (n == 1) puts("1");
else
{
// 用于标记是否是第一次输出质因数，初始为 true
bool first = true;
// 遍历从 2 到 n 的平方根的数（因为一个数的质因数不会超过它的平方根）
for (int i = 2; i <= n / i; i++)
// 判断 n 是否能被 i 整除，如果能整除，说明 i 是 n 的一个质因数
if (n % i == 0)
{
// 计算 n 能被质因数 i 整除的次数，即质因数 i 的幂次
int k = 0;
while (n % i == 0) n /= i, k++;
// 如果不是第一次输出质因数，先输出乘号 "*"
if (!first) cout << "*";
else first = false;
// 输出质因数 i
cout << i;
// 如果质因数 i 的幂次大于 1，输出幂次，格式为 "^k"
if (k > 1) cout << "^" << k;
}
// 如果经过前面的循环后，n 仍然大于 1，说明 n 本身就是一个大于其平方根的质因数
if (n > 1)
{
// 如果不是第一次输出质因数，先输出乘号 "*"
if (!first) cout << "*";
// 输出剩余的质因数 n
cout << n;
}
}
return 0;
}#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
// 定义一个常量，用于表示数组的最大大小，这里用于存储素数相关信息
const int maxn = 100010;
// 布尔类型数组，用于标记每个数是否为素数，初始值都设为false（0表示false）
// 后续会通过埃拉托斯特尼筛法来更新这些标记
bool isprime[maxn] = {0};
// 用于存储素数的数组
int prime[maxn];
// 记录素数的数量，初始值为0
int pnum = 0;
// 函数功能：使用埃拉托斯特尼筛法生成小于maxn的素数表
void findprime() {
// 初始化isprime数组，将所有大于等于2的数标记为可能是素数（设为true）
for (int i = 2; i < maxn; i++) {
isprime[i] = true;
}
// 遍历从2到maxn - 1的数
for (int i = 2; i < maxn; i++) {
// 如果当前数i被标记为素数
if (isprime[i]) {
// 将素数i存入prime数组中，并更新素数的数量pnum
prime[pnum++] = i;
// 将i的所有倍数标记为非素数（设为false）
for (int j = i + i; j < maxn; j += i) {
isprime[j] = false;
}
}
}
}
// 定义结构体factor，用于存储质因数及其个数
struct factor {
int x, cnt; // x表示质因子，cnt表示个数
};
int main() {
// 调用findprime函数生成素数表
findprime();
int n;
// 使用scanf函数从标准输入读取一个整数n，提高输入效率
scanf("%d", &n);
// 如果n等于1，按照题目要求输出"1=1"并换行
if (n == 1) {
printf("1=1\n");
} else {
// 按照题目要求，先输出n和等号，如："n="
printf("%d=", n);
// 计算n的平方根，用于后续确定质因数的查找范围
int sqr = (int)sqrt(1.0 * n);
// 使用vector动态数组fac来存储质因数及其个数
vector<factor> fac;
// 遍历素数表prime，查找n的质因数
for (int i = 0; i < pnum && prime[i] <= sqr; i++) {
// 如果当前素数prime[i]是n的质因数（n能被prime[i]整除）
if (n % prime[i] == 0) {
factor temp;
// 记录当前质因数
temp.x = prime[i];
// 初始化当前质因数的个数为0
temp.cnt = 0;
// 计算当前质因数的个数，即n能被prime[i]整除的次数
while (n % prime[i] == 0) {
temp.cnt++;
n /= prime[i];
}
// 将当前质因数及其个数存入fac数组中
fac.push_back(temp);
}
// 如果n已经被分解为1，说明质因数分解完成，退出循环
if (n == 1) break;
}
// 如果经过上述循环后，n仍然大于1，说明n本身就是一个大于其平方根的质因数
if (n != 1) {
factor temp;
temp.x = n;
temp.cnt = 1;
fac.push_back(temp);
}
// 遍历fac数组，按照题目要求的格式输出质因数分解的结果
for (size_t i = 0; i < fac.size(); i++) {
// 如果不是第一个质因数，先输出乘号"*"
if (i > 0) printf("*");
// 输出当前质因数
printf("%d", fac[i].x);
// 如果当前质因数的个数大于1，输出其指数，格式为"^个数"
if (fac[i].cnt > 1) {
printf("^%d", fac[i].cnt);
}
}
// 输出结束后换行
printf("\n");
}
return 0;
}#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
// 定义一个常量，用于表示数组的最大大小，这里用于存储素数相关信息
const int maxn = 100010;
// 布尔类型数组，用于标记每个数是否为素数，初始值都设为false（0表示false）
// 后续会通过埃拉托斯特尼筛法来更新这些标记
bool isprime[maxn] = {0};
// 用于存储素数的数组
int prime[maxn];
// 记录素数的数量，初始值为0
int pnum = 0;
// 函数功能：使用埃拉托斯特尼筛法生成小于maxn的素数表
void findprime() {
// 初始化isprime数组，将所有大于等于2的数标记为可能是素数（设为true）
for (int i = 2; i < maxn; i++) {
isprime[i] = true;
}
// 遍历从2到maxn - 1的数
for (int i = 2; i < maxn; i++) {
// 如果当前数i被标记为素数
if (isprime[i]) {
// 将素数i存入prime数组中，并更新素数的数量pnum
prime[pnum++] = i;
// 将i的所有倍数标记为非素数（设为false）
for (int j = i + i; j < maxn; j += i) {
isprime[j] = false;
}
}
}
}
// 定义结构体factor，用于存储质因数及其个数
struct factor {
int x, cnt; // x表示质因子，cnt表示个数
} fac[maxn]; // 定义一个足够大的数组来存储质因数及其个数
int main() {
// 调用findprime函数生成素数表
findprime();
int n;
// 使用scanf函数从标准输入读取一个整数n，提高输入效率
scanf("%d", &n);
// 如果n等于1，按照题目要求输出"1=1"并换行
if (n == 1) {
printf("1=1\n");
} else {
// 按照题目要求，先输出n和等号，如："n="
printf("%d=", n);
// 计算n的平方根，用于后续确定质因数的查找范围
int sqr = (int)sqrt(1.0 * n);
int num = 0; // 用于记录质因数的个数
// 遍历素数表prime，查找n的质因数
for (int i = 0; i < pnum && prime[i] <= sqr; i++) {//如果当前素数prime[i]是n的质因数（n能被prime[i]整除）
if (n % prime[i] == 0) {
fac[num].x = prime[i];
fac[num].cnt = 0;
// 计算当前质因数的个数，即n能被prime[i]整除的次数
while (n % prime[i] == 0) {
fac[num].cnt++;
n /= prime[i];
}
num++;
}
// 如果n已经被分解为1，说明质因数分解完成，退出循环
if (n == 1) break;
}
// 如果经过上述循环后，n仍然大于1，说明n本身就是一个大于其平方根的质因数
if (n != 1) {
fac[num].x = n;
fac[num].cnt = 1;
num++;
}
// 遍历fac数组，按照题目要求的格式输出质因数分解的结果
for (int i = 0; i < num; i++) {
// 如果不是第一个质因数，先输出乘号"*"
if (i > 0) printf("*");
// 输出当前质因数
printf("%d", fac[i].x);
// 如果当前质因数的个数大于1，输出其指数，格式为"^个数"
if (fac[i].cnt > 1) {
printf("^%d", fac[i].cnt);
}
}
// 输出结束后换行
printf("\n");
}
return 0;
}
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
// 增大数组大小以适应更大范围的素数，定义一个常量表示数组的最大长度，用于素数表和质因数存储数组的大小
const int maxn = 100010;
// 判断n是否为素数的函数，参数n为长整型
bool isprime(long long n) {
// 如果n等于1，根据素数定义，1不是素数，直接返回false
if (n == 1) return false;
// 计算n的平方根，并转换为长整型，用于后续循环判断的上限
long long sqr = (long long)sqrt(1.0 * n);
// 从2到n的平方根遍历，检查是否存在能整除n的数
for (long long i = 2; i <= sqr; i++) {
// 如果存在能整除n的数，则n不是素数，返回false
if (n % i == 0) return false;
}
// 如果遍历完都没有找到能整除n的数，则n是素数，返回true
return true;
}
// 用于存储素数的数组，数组元素为长整型，以适应较大的素数
long long prime[maxn];
// 记录素数在prime数组中的数量
int pnum = 0;
// 求素数表的函数，即找出一定范围内的所有素数并存入prime数组
void findprime() {
// 从2开始遍历到maxn - 1
for (long long i = 2; i < maxn; i++) {
// 如果当前数i是素数
if (isprime(i)) {
// 将素数i存入prime数组，并更新素数数量pnum
prime[pnum++] = i;
}
}
}
// 定义结构体factor，用于存储质因数及其个数
struct factor {
long long x; // 存储质因数，为长整型以适应较大的质因数
int cnt; // 存储质因数的个数
} fac[maxn];
int main() {
// 调用findprime函数生成素数表
findprime();
long long n;
// 使用scanf函数从标准输入读取一个长整型整数n，提高输入效率
scanf("%lld", &n);
// 如果n等于1，按照题目要求输出"1=1"并换行
if (n == 1) {
printf("1=1\n");
} else {
// 按照题目要求，先输出n和等号，如："n="
printf("%lld=", n);
// 计算n的平方根，并转换为长整型，用于后续质因数查找的范围判断
long long sqr = (long long)sqrt(1.0 * n);
int num = 0; // 用于记录质因数的个数
// 遍历素数表prime，查找n的质因数
for (int i = 0; i < pnum && prime[i] <= sqr; i++) {
// 如果当前素数prime[i]是n的质因数（即n能被prime[i]整除）
if (n % prime[i] == 0) {
fac[num].x = prime[i]; // 记录当前质因数
fac[num].cnt = 0; // 初始化当前质因数的个数为0
// 计算当前质因数的个数，即n能被prime[i]整除的次数
while (n % prime[i] == 0) {
fac[num].cnt++;
n /= prime[i];
}
num++; // 质因数个数加1
}
// 如果n已经被分解为1，说明质因数分解完成，退出循环
if (n == 1) break;
}
// 如果经过上述循环后，n仍然大于1，说明n本身就是一个大于其平方根的质因数
if (n != 1) {
fac[num].x = n; // 记录这个质因数
fac[num].cnt = 1; // 这个质因数的个数为1
num++;
}
// 遍历fac数组，按照题目要求的格式输出质因数分解的结果
for (int i = 0; i < num; i++) {
// 如果不是第一个质因数，先输出乘号"*"
if (i > 0) printf("*");
// 输出当前质因数
printf("%lld", fac[i].x);
// 如果当前质因数的个数大于1，输出其指数，格式为"^个数"
if (fac[i].cnt > 1) {
printf("^%d", fac[i].cnt);
}
}
// 输出结束后换行
printf("\n");
}
return 0;
}#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
// 定义大整数结构体bign
struct bign{
int d[1000]; // 用于存储大整数的每一位数字，数组长度为1000
int len; // 记录大整数的位数
bign(){
// 初始化函数，将数组d的所有元素置为0
memset(d,0,sizeof(d));
len = 0; // 初始化大整数的位数为0
}
};
// 将字符数组表示的数转换为bign结构体表示的大整数
bign change(char str[]){
bign a;
a.len = strlen(str); // 获取字符数组的长度，即大整数的位数
for(int i=0;i<a.len;i++){
// 将字符数组中的字符转换为对应的数字，并逆序存储到bign结构体的数组d中
a.d[i] = str[a.len-i-1] - '0';
}
return a; // 返回转换后的大整数
}
// 实现两个大整数相加的函数
bign add(bign a,bign b){
bign c;
int carry = 0; // 进位变量，初始值为0
// 遍历两个大整数的每一位，直到两个大整数的所有位都处理完毕
for(int i=0;i<a.len||i<b.len;i++){
// 计算当前位的和，包括两个大整数对应位的数字以及进位
int temp = a.d[i] + b.d[i] + carry;
c.d[c.len++] = temp % 10; // 将当前位的和的个位数存入结果大整数c的数组d中，并更新位数
carry = temp / 10; // 更新进位
}
// 如果最后还有进位，将进位存入结果大整数c的数组d中，并更新位数
if(carry!=0){
c.d[c.len++] = carry;
}
return c; // 返回相加后的大整数
}
// 用于输出大整数的函数
void print(bign a){
// 从大整数的最高位开始，依次输出每一位数字
for(int i=a.len-1;i>=0;i--){
printf("%d",a.d[i]);
}
}
int main(){
char str1[1000],str2[1000];
// 从标准输入读取两个字符数组，用于表示两个大整数
scanf("%s%s",str1,str2);
bign a = change(str1); // 将字符数组str1转换为大整数a
bign b = change(str2); // 将字符数组str2转换为大整数b
print(add(a,b)); // 计算大整数a和b的和，并输出结果
return 0;
}