算法竞赛中的基本数论

（for循环可做）

（分析最大公约数，但实际用不到辗转相除法）

（暴力判断素数）

#include<bits/stdc++.h>
using namespace std;
bool prime(int a){if (a <= 1) return 0;for(int i = 2;i * i <= a;i++){if(a % i == 0) return 0;}return 1;
}
int main(){int a,b;bool x = 1;cin >> a >> b;for(int i = a;i <= b;i++){int re = i;x = 1;while(re){if(!prime(re)){x = 0;break;} re /= 10;}if(x) cout << i << endl;}return 0;
}

（暴力判断素数）

题目分析

求包含不同的质因子数最多的数。那就累乘所有的质因子呗，累乘的过程不能超过给定的n。因为有多次询问，我们可以把质数都预处理出来。

题目代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int step=0;int[] a=new int[100005];for(int i=2;i<=10000;i++)//找出所有的质数{if(check(i)){a[++step]=i;}}int t=sc.nextInt();while(t-->0){long n=sc.nextLong();double now=1;int ans=0;for(int i=1;i<=step;i++){now=now*a[i];ans++;if(now>=n){break;}}if(now==n){System.out.println(ans);}else{System.out.println(ans-1);}}}public static boolean check(int i){for(int j=2;j<=Math.sqrt(i);j++){if(i%j==0)return false;}return true;}
}

题目分析

既然对长度有要求，那么可以优先遍历子段的长度，然后遍历右端点，这样可以唯一的确定一个子段，然后使用前缀和快速求出子段的和，虽然是两层嵌套for循环，但是由于质数的个数很少，所以第二层循环执行的次数要比n小的多，所以可以通过。

题目代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long n = scan.nextLong();long max = Integer.MIN_VALUE;long[]a = new long[(int)(n+1)];for (int i = 1; i <= n; i++) {a[i] = scan.nextLong();a[i] += a[i-1];}for(int i = 2; i <= n;i++){if(isprime(i)){for(int j = i; j <= n; j++){max = Math.max(a[j]-a[j-i],max);}}}System.out.println(max);scan.close();}public static boolean isprime(long len){for(int i = 2; i*i <= len; i++){if(len % i == 0) return false;}return true;}
}

（最大公约数）

（最小公倍数）

（好在数据范围小，可以直接枚举）

（需要仔细想一下）

（还要了解到两个数的乘积就是这两个数最大公约数和最小公倍数的乘积）

（还挺难的，要画图进行模拟分析，最后是要确定两个数字是否互质）

(数学推导)

题目分析：

$M=gcd(b_1,b_2......b_n)$，则$M<=minb$，其中$minb$表示所有的$b_i$中的最小值。又因为$1<b_i<=a_i$，所以$minb$能够取到的最大值是$a_i$的最小值，所以$M$可以取到的最大值是$a_i$的最小值。什么情况下$M<=mina$呢？即$b_i$是$mina$的倍数，那么对于$mina$对应的$b_i$必然等于$mina$。其他值可以是$c\ast mina$但是不能超过它对应的$a_i$的值，因此每个位置可以取值的个数为$a_i/mina$，这里下取整，可能的方案数是所有位置可以取值的个数的累乘。

题目代码：

#include <iostream>
using namespace std;
int a[100050],n,mgcd=1<<30;
const int mod=1e9+7;
int main()
{cin >> n;for (int i=1;i<=n;i++){cin >> a[i];mgcd=min(mgcd,a[i]);}long long ans=1;for (int i=1;i<=n;i++)ans=(long long)ans*(a[i]/mgcd)%mod;cout << mgcd << " " << ans << endl;return 0;
}

题目分析

题目代码

import java.util.*;
public class Main {public static void main(String[] args) {int ans = 0;for(int i = 1 ; i <= 2020 ; i ++){for(int j = 1 ; j <= 2020 ; j ++){if(gcd(i , j) == 1) ans ++;}}System.out.println(ans);}static int gcd(int a,int b){if(b == 0) return a;else return gcd(b , a % b);}
}

题目分析

根据题目描述，其实是求解一元线性同余方程组
$$x\equiv a_1(mod{m}_1)$$

$$x\equiv a_2(mod{m}_2)$$

$$x\equiv a_3(mod{m}_3)$$

$$......$$

$$x\equiv a_n(mod{m}_n)$$

如果$x$是方程组的一个解，那么$x+k\ast lcm(m_1,m_2,m_3...m_n)$是方程组的一个通解。

因此我们可以先求第一个式子的解$x_1$，那么第二个式子的解应该是在$x_1+k\ast lcm(x_1,1)$里去找，这样才能保证得到的解依然是第一个式子的解，假设第一个式子和第二个式子的解是$x_2$，那么第三个式子的解应该是在$x_2+k\ast lcm(x_1,x_2)$里去找，这样才能保证得到的解依然是第一个式子和第二个式子的解。 依次类推即可。

题目代码

import java.util.*;
import java.io.*;
public class Main {//求数字a,b的最大公约数public static long gcd(long a, long b) {if (b == 0) return a;return gcd(b, a % b);}//求数字a,b的最小公倍数public static long lcm(long a, long b){return a / gcd(a, b) * b;}public static void main(String[] args) {Scanner in = new Scanner(System.in);long[] a = {0, 0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46};long x = 0, step = 1;for(int i = 2; i <= 49; i++){//暴力求解满足x % i = a[i]while(x % i != a[i])x += step;step = lcm(step, i);}System.out.println(x);}
}

题目分析

唯一分解定理的直接应用

约数？？？？因数，因子

$n=p_1^2+p_2^3$

求n的所有因子的个数

$36=2^2\ast 3^2$

1($2^0\ast 3^0$) 36($2^2\ast 3^2$)

2($2^1\ast 3^0$) 18($2^1\ast 3^2$)

3 12

4 9

6

$2^i\ast 3^j$

0-2 3种

0-2 3种

36的所有的因子个数

题目代码

#include <iostream>
using namespace std;
int main() {long long n;cin >> n; // 输入n 分解为多个质因子相乘的形式long long sum = 0;   for (long long i = 2; i * i <= n; i++) {if (n % i == 0) {sum++;  // i 是 n 的一个质因子}while (n % i == 0) {n = n / i;  // 一直除以 i，直到不能被整除}}// 如果n大于1，说明剩下的n是质数if (n > 1) {sum++;}cout << sum << endl;  // 输出质因子个数return 0;
}

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();long sum = 0;for (long i = 2; i * i <= n; i++) {if (n % i == 0) sum++;while (n % i == 0)n = n / i;}if(n > 1) sum++;System.out.println(sum);}
}

题目分析：

题目代码：

#include <iostream>
#include <cmath>
using namespace std;int main() {long long n = 1200000;int ans = 1;// 从2开始判断每个可能的因子for (int i = 2; i <= sqrt(n); i++) {int cnt = 0;// 除尽所有 i 的倍数while (n % i == 0) {n = n / i;cnt++;}// 计算该质因子的因子个数ans *= (cnt + 1);}// 如果n大于1，说明剩下的n是质数if (n > 1) {ans *= 2;}cout << ans << endl;  // 输出结果return 0;
}

import java.util.Scanner;public class Main{
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = 1200000;int ans = 1;for (int i = 2; i <= Math.sqrt(n); i++) {int cnt = 0;while(n%i == 0) {n = n / i;cnt++;}ans *=(cnt+1);}if(n > 1) {ans *= 2;}System.out.println(ans);
}
}

问题描述
定义阶乘 n! = 1 × 2 × 3 × ··· × n。

请问 100! （100 的阶乘）有多少个约数。

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题目分析

这是蓝桥杯国赛的一道原题。求一个数的约数个数可以用唯一分解定理在$O(\sqrt{n})$的时间复杂度内求解。但是100的阶乘确实有点大了，你要是把100的阶乘求出来再去求会超时，并且这个数的存储也是一个问题，当然用java的大整数是可以存的。

这里只能舍弃掉求100的阶乘再求它的约数个数的思路，那应该怎么求呢？回顾一下利用唯一分解定理求解约数个数的过程，先对数字n进行质因数分解，得到式子$n=p_0^{j_0}\ast p_1^{j_1}\ast p_2^{j_2}...\ast p_k^{j_k}$，然后可以求得n的因子个数为$(j_0+1)\ast (j_1+1)\ast (j_2+1)...\ast (j_k+1)$。其实我们只需要知道数字n里面包含几个$p_i$即可。对于$100!=1\ast 2\ast 3\ast \mathrm{4...}\ast 100$，我们可以计算出2里面包含数字2的个数为$a_1$，3里面包含数字2的个数为$a_2$，4里面包含数字2的个数为$a_3$，5里面包含数字2的个数为$a_4$，以此类推直到求到100，那么100!里面包含数字2的个数就是$a_1+a_2+a_3...a_{99}$。综上我们可以依次对1到100里面的每一个数进行质因数分解，得到的值累加就可以了，最终就可以求出来100进行质因子分解的结果。然后再按照求因子个数的方法进行求解就可以了。

题目代码

public class Main {
public static void main(String[] args) {int p[] = new int[105];for(int i = 2;i <= 100;i++) {int n = i;for(int j = 2;j * j <= n;j++) {while(n%j==0) {p[j]++;n/=j;}}if(n > 0) p[n]++;}long ans = 1;for(int i = 2;i <= 100;i++) {ans *= (p[i]+1);}System.out.println(ans);
}
}

#include <iostream>
using namespace std;
int p[100];
int main()
{for (int i = 2; i <= 100; i ++){int n = i;for (int j = 2; j <= n / j; j ++)while(n % j == 0){p[j] ++;n /= j;}if(n > 1) p[n] ++;    }long ans = 1;for (int i = 2; i <= 100; i ++)if(p[i]) ans *= (p[i] + 1);cout << ans << endl;return 0;    
}

问题描述
学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可
以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并
把它定义为 $S_t$ 。
例如 $S_1$ = 1, $S_2$ = 2, $S_3$ = 4, $S_4$ = 6，···。
现在小明想知道，前 60 个 $S_i$ 的和是多少？即 $S_1+S_2+\cdot \cdot \cdot +S_{60}$ 是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题目分析1

这也是蓝桥杯国赛的一道真题。参考题解

考虑一下i=12时怎么求解$S_i$，

$12=6\ast 2$ $S_i=2^5\ast 3^1$

$12=3\ast 2\ast 2$ $S_i=2^3\ast 3^1\ast 5^1$

$12=4\ast 3$ $S_i=2^3\ast 3^2$

$12=2\ast 2\ast 3$ $S_i=2^1\ast 3^1\ast 5^2$

假设数字n的因数个数有12个，那么根据12的分解结果，可以推出来$S_i$的值（每个乘数间1就是要求的数分解后的质数的幂次），但是这个值并不是唯一的，不同的分解结果有不同的值，同一个分解结果不同的幂次分配方式也对应不同的值。比如$12=2\ast 2\ast 3$这种分解结果，如果想要n的值比较小，那么就把这几个数字分配到前3小的质数上，即$S_i=2^1\ast 3^1\ast 5^2$。但是这不是最理想的分配方式。我们将3,2,2降序排序，再减一为2,1,1，那么显然$S_i=2^2\ast 3^1\ast 5^1$要比之前求的$S_i=2^1\ast 3^1\ast 5^2$更小。

总结一下这道题的解题步骤，对于$S_i$，我们dfs搜出i所有的分解情况，然后按照刚刚的办法即对分解降序后求出$S_i$。这样一种分解对应一个值，所有的分解对应的值里面求最小值就是$S_i$。

另外，特判因子数为质数，比如因子数是13，减一是12，这个幂次全部分配给2就是我们要找的最小数。

题目代码1

import java.math.BigInteger;
public class Main {static int n=10000;static int  prime[]=new int[n];static int index=0;static BigInteger endBigInteger=new BigInteger("99999999999999999999999999999999999");public static void main(String[] args) {int vis[]=new int[n];for (int i = 2; i <n; i++) {if (vis[i]==0) {prime[index]=i;index++;for (int j = i*i; j <n; j+=i) {vis[j]=1;}}}BigInteger sumBigInteger=new BigInteger("0");for (int i = 1; i <=60; i++) {int vis1[]=new int[i+1];dfs(i,i,0,vis1);sumBigInteger=sumBigInteger.add(endBigInteger);endBigInteger=new BigInteger("99999999999999999999999999999999999");}System.out.println(sumBigInteger);}static void dfs(int Snum,int mid,int start,int vis[]) {if (mid==1) {if (endBigInteger.compareTo(loop(Snum, vis))==1) {endBigInteger=loop(Snum, vis);}return;}for (int i = 2; i <=mid; i++) {if (mid%i==0) {vis[i]++;dfs(Snum,mid/i, start, vis);dfs(Snum,mid/i, start+1, vis);vis[i]--;}}}static BigInteger loop(int num,int vis[]) {int vis2[]=new int[vis.length];for (int i = 0; i < vis.length; i++) {vis2[i]=vis[i];}int index2=0;BigInteger sumBigInteger=new BigInteger("1");for (int i =vis2.length-1; i>0; i--) {if (vis2[i]>0) {sumBigInteger=sumBigInteger.multiply(new BigInteger(prime[index2++]+"").pow(i-1));vis2[i]--;i=i+1;}}return sumBigInteger;}
}

题目分析2

刚刚的分析是比较正规但是也比较麻烦的思路，这道题还有另外一种讨巧的思路。$S_i$最多由4个质数构成，要使值最小那么这4个质数必然是2，3，5，7。我只需要枚举2，3，5，7对应的幂次就可以了。在枚举的过程中记录当前有t个约数的值，和之前记录的值取一个最小。最后求和输出就行。

题目代码2

import java.util.*;
public class Main {static int testCount=60;static int ii=100;static long result[]=new long[61];public static void main(String[] args) {for (int a4 = 0; a4 <= ii; a4++) {for (int a3 = 0; a3 <= ii; a3++) {for (int a2 = 0; a2 <= ii; a2++) {for (int a1 = 0; a1 <= ii; a1++) {int t=(a1+1)*(a2+1)*(a3+1)*(a4+1);if(t<=60) {long single=(long) (Math.pow(2, a1)*Math.pow(3, a2)*Math.pow(5, a3)*Math.pow(7, a4));if(single<result[t] || result[t]==0) {result[t]=single;}}}}}}long sum=0;for (int i = 1; i <= testCount; i++) {sum+=result[i];}System.out.println(sum);}
}

题目分析

ans表示答案（约数和）

（1）求n！内包含的质数个数

阶乘末尾包含0的个数，n！包含5的个数 （通过while循环求）

(2)n以内的质数有谁都求出来 （欧拉筛）

$1\ast 2\ast 3\ast \mathrm{4...}\ast n$

(3)对于质数p，有m个

$ans\ast =(1-p^{m+1})/(1-p)$

和阶乘约数一样，把阶乘求出来再进行分解不现实，我们只需要知道阶乘里面含有质因子的个数就可以了。一个数的阶乘里面含有某个数的个数，在题目里有遇见过，那里求的是n的阶乘含有5的个数，但是换成其他数字也是同样的道理。

首先把n以内的所有质数找出来，然后遍历n以内的所有质数，统计n！含有该质数的个数。

至于约数和，根据（2）的介绍，有
$$sum=(p_0^0+p_0^1+...+p_0^{j_0})\ast (p_1^0+p_1^1+...+p_1^{j_1})\ast ...\ast (p_k^0+p_k^1+...+p_k^{j_k})$$
对于每一个乘积项其实是关于质数的等比数列求和，如下所示
$$\frac{p_i^{j_i+1}-1}{p_i-1}$$
因为题目有取余操作，所以需要求$p_i-1$的逆元。

等比数列求和公式
$$\frac{a_1\ast (1-q^n)}{1-q}$$

题目代码

import java.util.Arrays;
import java.util.Scanner;public class Main {static Scanner in = new Scanner(System.in);static int n, k, zu;static int N = (int) (2e5 + 10);static int prime[]=new int[N];static boolean st[]=new boolean[N];static int cnt=0;static int mod=998244353;static void solve() {n=in.nextInt();long ans=1;for(int i=0;prime[i]<=n;i++){long res=0;int x=n;while(x!=0){res=res+x/prime[i];//直接求n！里面含有prime的个数x/=prime[i];}ans=(ans*((ksm(prime[i],res+1,mod)-1)*ksm(prime[i]-1,mod-2,mod)%mod)+mod)%mod;}System.out.println(ans);}static void getPrime(int n) {cnt = 0;for (int i = 2; i <= n; i++) {if (!st[i]) prime[cnt++] = i;for (int j = 0; j < cnt; j++) {if ((long) i * prime[j] > n) break;st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}}static long ksm(long a, long b, long p) {long res = 1;for (; b != 0; b >>= 1, a = a * a % p) {if ((b & 1) == 1) {res = res * a % p;}}return res;}public static void main(String[] args) {Arrays.fill(prime,0x3f3f3f3f);getPrime(200000);int t = 1;for (zu = 1; zu <= t; zu++) {solve();}}
}

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>using namespace std;const int N = 2e5 + 10;
const int mod = 998244353;int n, k, zu;
int prime[N];
bool st[N];
int cnt = 0;long long ksm(long long a, long long b, long long p) {long long res = 1;while (b != 0) {if (b & 1) {res = res * a % p;}a = a * a % p;b >>= 1;}return res;
}void getPrime(int n) {cnt = 0;for (int i = 2; i <= n; i++) {if (!st[i]) prime[cnt++] = i;for (int j = 0; j < cnt; j++) {if ((long long)i * prime[j] > n) break;st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}void solve() {cin >> n;long long ans = 1;for (int i = 0; prime[i] <= n; i++) {long long res = 0;int x = n;while (x != 0) {res += x / prime[i];  // 直接求n！里面含有prime的个数x /= prime[i];}ans = (ans * ((ksm(prime[i], res + 1, mod) - 1) * ksm(prime[i] - 1, mod - 2, mod) % mod) + mod) % mod;}cout << ans << endl;
}int main() {fill(prime, prime + N, 0x3f3f3f3f);getPrime(200000);int t = 1;for (zu = 1; zu <= t; zu++) {solve();}return 0;
}

参考代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;public class 最小质因子之和Easy {
public static void main(String[] args) throws IOException{//进行预处理f();//求2-n每个数对应的最小质因子sum();//求前缀和数组StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); Scanner scanner = new Scanner(System.in);sc.nextToken();int t = (int)sc.nval;while(t-- >0) {sc.nextToken();int n = (int)sc.nval;System.out.println(res[n]);}
}
static int book[] = new int[4000000];
static int pre[] = new  int[4000000];
private static void f() {//埃氏筛模板//每个数的最小质因子//pre[i]表示i的最小质因子book[1] = 1;//记录是否为素数，1表示不是素数book[0] = 1;for(int i =2;i<book.length;i++) {if(book[i]==0) {// i是素数，筛掉素数的倍数 i=2 6 = 2+2+2pre[i] = i;//求的是质数的最小质因子for(int j = i+i;j<book.length&&j>0;j+=i) {if(book[j]==0) {pre[j] =i;}book[j] = 1;}}}}
static long res[] = new long[4000000];
private static void sum() {//一次求出i 2- n// 2-i的最小质因子之和，前缀和数组可以在O（n）for(int i=2;i<res.length;i++) {res[i] = res[i-1]+pre[i];}
}
}

#include <iostream>
#include <vector>
using namespace std;const int MAX_N = 4000000;int book[MAX_N]; // book[i] = 0 表示 i 是质数，1 表示 i 不是质数
int pre[MAX_N];  // pre[i] 表示 i 的最小质因子
long long res[MAX_N]; // res[i] 表示 2 到 i 的最小质因子之和void f() {// 埃氏筛法，求最小质因子book[0] = book[1] = 1; // 0 和 1 不是质数for (int i = 2; i < MAX_N; ++i) {if (book[i] == 0) { // 如果 i 是质数pre[i] = i; // i 的最小质因子是它本身for (int j = i + i; j < MAX_N; j += i) { // 筛掉 i 的倍数if (book[j] == 0) {pre[j] = i;}book[j] = 1; // 标记 j 不是质数}}}
}void sum() {// 计算前缀和，res[i] 表示 2 到 i 的最小质因子之和for (int i = 2; i < MAX_N; ++i) {res[i] = res[i - 1] + pre[i];}
}int main() {// 进行预处理f();sum();int t;cin >> t;  // 输入测试用例数while (t--) {int n;cin >> n; // 输入 ncout << res[n] << endl; // 输出结果}return 0;
}

参考代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class 最小质因子之和Hard {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int[] prime = new int[20000005];int[] f = new int[20000005];boolean[] visit = new boolean[20000005];int count = 0;for (int i = 2; i < 20000005; i++) {//线性if (!visit[i]) {//如果i是一个质数prime[count++] = i;f[i] = i;}for (int j = 0; j < count && i * prime[j] < 20000005; j++) {visit[i * prime[j]] = true;f[i * prime[j]] = prime[j];if (i % prime[j] == 0) break;}}long[] sum = new long[20000005];//前缀和数组for (int i = 2; i < f.length; i++) {//System.out.println(f[i]);sum[i] = sum[i - 1] + f[i];}int t = Integer.parseInt(br.readLine());while (t-- > 0) {int n = Integer.parseInt(br.readLine());System.out.println(sum[n]);}}
}

#include <iostream>
#include <vector>
using namespace std;const int MAX_N = 20000005;int prime[MAX_N];   // 存储质数
int f[MAX_N];       // 存储每个数的最小质因子
bool visit[MAX_N]; // 用于标记已访问的数
long long sum[MAX_N]; // 存储前缀和void sieve() {int count = 0;for (int i = 2; i < MAX_N; i++) {if (!visit[i]) { // 如果 i 是质数prime[count++] = i;f[i] = i;}for (int j = 0; j < count && i * prime[j] < MAX_N; j++) {visit[i * prime[j]] = true;f[i * prime[j]] = prime[j];if (i % prime[j] == 0) break;}}
}void compute_prefix_sum() {for (int i = 2; i < MAX_N; i++) {sum[i] = sum[i - 1] + f[i]; // 计算前缀和}
}int main() {// 执行预处理sieve();compute_prefix_sum();int t;cin >> t; // 输入测试用例数while (t--) {int n;cin >> n; // 输入 ncout << sum[n] << endl; // 输出前缀和结果}return 0;
}

题目分析：

题目代码：

#include<bits/stdc++.h>
using namespace std;
string a,b,c;
vector<int> add(vector<int>A,vector<int>B){if(A.size()<B.size())return add(B,A);int t=0;vector<int>C;for(int i=0;i<A.size();i++){t+=A[i];if(i<B.size())t+=B[i];C.push_back(t%10);t/=10;}if(t)C.push_back(t);return C;
}
int main (){int n=1;//cin>>n;for(int i=0;i<n;i++){vector<int>A,B;cin>>a>>b;for(int i=a.size()-1;i>=0;i--){A.push_back(a[i]-'0');}for(int i=b.size()-1;i>=0;i--){B.push_back(b[i]-'0');}vector<int>C=add(A,B);for(int i=C.size()-1;i>=0;i--){cout << C[i];}cout<<endl;}	return 0;
}

字符数组写法

#include <iostream>
#include<cstring>
using namespace std;
const int maxn = 100;
char a1[maxn],b1[maxn];
int a[maxn],b[maxn],c[maxn];
int main() {cin>>a1;cin>>b1;int lena = strlen(a1);int lenb = strlen(b1);for(int i=0,j=lena-1;i<lena;i++,j--)a[j]=a1[i]-'0';for(int i=0,j=lenb-1;i<lenb;i++,j--)b[j]=b1[i]-'0';int lenc = lena>lenb?lena:lenb;for(int i = 0;i < lenc;i++){c[i]+=a[i]+b[i];if(c[i] >= 10){c[i+1]=c[i]/10;c[i]=c[i]%10;}}if(c[lenc]>0) lenc++;for(int i = lenc-1;i>=0;i--)cout<<c[i];return 0;
}

题目分析：

题目代码：

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb push_back
vi sub(vi a,vi b){vi res;int t=0;for (int i=0;i<a.size();i++){t+=a[i];if (i<b.size()) t-=b[i];res.pb((t+10)%10);if (t<0) t=-1;else t=0;}while (res.size()>1 && res.back()==0) res.pop_back();return res;
}
int main(){int n=1;string q[51],p[51];//cin>>n;for (int i=1;i<=n;i++) cin>>q[i]>>p[i];for (int j=1;j<=n;j++){vi a,b;if (q[j].size()<p[j].size() || q[j].size()==p[j].size() and q[j]<p[j]){cout<<"-";swap(q[j],p[j]);}for (int i=q[j].size()-1;i>=0;i--) a.pb(q[j][i]-48);for (int i=p[j].size()-1;i>=0;i--) b.pb(p[j][i]-48);auto c=sub(a,b);for (int i=c.size()-1;i>=0;i--) cout<<c[i];cout<<endl;}return 0;	
}

题目分析：

题目代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> a,b;
string x,y;
vector<int> mul(vector<int> a,vector<int> b){vector<int> res;for(int i = 0;i < a.size();i++){for(int j = 0;j < b.size();j++){if(i+j<res.size()) res[i+j]+=a[i]*b[j];else res.push_back(a[i]*b[j]);}}//处理进位int t = 0;for(int i = 0;i < res.size();i++){t += res[i];//这个t里面可能携带进位res[i]=t%10;//留下的结果t /= 10;//计算当前位的进位}//特殊处理最后一位的进位while(t){res.push_back(t%10);t/=10;}//处理前导0while(res.size()>1&&res.back()==0) res.pop_back();//返回结果return res;
}
int main(){cin>>x>>y;for(int i = x.size()-1;i>=0;i--) a.push_back(x[i]-'0');for(int i = y.size()-1;i>=0;i--) b.push_back(y[i]-'0');vector<int> c = mul(a,b);for (int i=c.size()-1;i>=0;i--) cout<<c[i];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int res[202];
void m(int a[],int b[],int &j){for(int i = 0;i < 100;i++){for(int j = 0;j < 100;j++){res[i+j] += a[i] * b[j];}}int t = 0;for(int i = 0;i <= j;i++){t += res[i];res[i] = t % 10;t /= 10;}while(t){res[++j] = t % 10;t /= 10;}while(j > 0 && res[j] == 0){j--;}return ;
}
int main(){char x[101],y[101];cin >> x >> y;int j = strlen(x)+strlen(y)-2;//计算错误int a[101]={0},b[101]={0};//初始化错误int k = 0;for(int i = strlen(x)-1;i >= 0;i--){a[k++] = x[i] - '0';//cout<<x[i]-'0'<<" ";}//cout<<endl;k = 0;for(int i = strlen(y)-1;i >= 0;i--){b[k++] = y[i] - '0';//cout<<y[i]-'0'<<" ";}//cout<<endl;m(a,b,j);//未调用函数for(int i = j;i >= 0;i--){cout << res[i];}return 0;
}