pat学习笔记

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]);}}
}

2-SUM-双指针

优化算法如下：该算法的时间复杂度为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 的长度 mscanf("%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]存放至临时变量tempwhile(left<right){//只要left与rightwhile(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]存放至临时变量tempwhile(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;
}

 

1040 有几个PAT

#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;
}    

1019 数字黑洞

#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 就是最大公约数，直接返回 aif (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 开始遍历到 nfor (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数组中，并更新素数数量pnumprime[pnum++] = i; // 从i的2倍开始，将i的所有倍数标记为合数（即p[j]设为true）for (int j = i + i; j < maxn; j += i) { p[j] = true;}}}
}int main() {// 从标准输入读取一个整数ncin >> n; // 调用findprime函数筛选小于等于n的素数findprime(); // 遍历prime数组，输出所有找到的素数for (int i = 0; i < pnum; i++) { printf("%d\n", prime[i]);}return 0;
}

 1013 数素数

#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 数组中，并更新素数的数量 numprime[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;
}

1059 Prime Factors

#include<bits/stdc++.h>
using namespace std;int main()
{int n;// 从标准输入读取一个整数 ncin >> n;// 输出格式：先输出 "n="printf("%d=", n);// 如果 n 等于 1，直接输出 "1" 并换行if (n == 1)    puts("1");else{// 用于标记是否是第一次输出质因数，初始为 truebool 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;// 输出质因数 icout << i;// 如果质因数 i 的幂次大于 1，输出幂次，格式为 "^k"if (k > 1) cout << "^" << k;}// 如果经过前面的循环后，n 仍然大于 1，说明 n 本身就是一个大于其平方根的质因数if (n > 1){// 如果不是第一次输出质因数，先输出乘号 "*"if (!first)  cout << "*";// 输出剩余的质因数 ncout << 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数组中，并更新素数的数量pnumprime[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];// 初始化当前质因数的个数为0temp.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数组中，并更新素数的数量pnumprime[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不是素数，直接返回falseif (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不是素数，返回falseif (n % i == 0) return false;}// 如果遍历完都没有找到能整除n的数，则n是素数，返回truereturn true;
}// 用于存储素数的数组，数组元素为长整型，以适应较大的素数
long long prime[maxn];
// 记录素数在prime数组中的数量
int pnum = 0;// 求素数表的函数，即找出一定范围内的所有素数并存入prime数组
void findprime() {// 从2开始遍历到maxn - 1for (long long i = 2; i < maxn; i++) {// 如果当前数i是素数if (isprime(i)) {// 将素数i存入prime数组，并更新素数数量pnumprime[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; // 这个质因数的个数为1num++;}// 遍历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];  // 用于存储大整数的每一位数字，数组长度为1000int len;      // 记录大整数的位数bign(){// 初始化函数，将数组d的所有元素置为0memset(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转换为大整数abign b = change(str2);  // 将字符数组str2转换为大整数bprint(add(a,b));  // 计算大整数a和b的和，并输出结果return 0;
}