高精度模板_牛客博客

N!
思路：模拟乘法

#include<iostream>
using namespace std;

const int maxn = 100000+10;
int a[maxn];

int main()
{
    int n;
    while (cin >> n) {
        int count = 1;
        a[0] = 1;
        int i;
        for ( i = 1; i <= n; i++) {
            int k = 0;
            for (int j = 0; j < count; j++) {
                int temp = i * a[j] + k;
                a[j] = temp % 10;
                k = temp / 10;
            }
            while (k) {
                a[count++] = k % 10;
                k /= 10;
            }
        }
        while (!a[i]) {
            if (a[i--])
                break;
        }
        for (int i = count - 1; i >= 0; i--) {
            cout << a[i];
        }
        cout << endl;
    }
}

求 A/B 高精度值(ab)
思路：模拟除法

#include"pch.h"
#include<iostream>
#include<string.h>
using namespace std;
int a[20];
int main()
{
	int x, y;
	while (cin >> x >> y) {
		memset(a, 0, sizeof(a));
		a[0] = x / y;
		if (x%y == 0) {
			cout << x << "/" << y << "=" << a[0] << endl;;
			continue;
		}
		else {
			int i;
			int temp = x % y;
			cout << x << "/" << y << "=" << a[0]<<".";
			for ( i = 1; i < 20; i++) {
				temp = temp * 10;
				a[i] = temp / y;
				temp = temp % y;
			}
			while (!a[i]) {
				if (a[i--])
					break;
			}
			for (int j = 1; j <= i; j++) {
				cout << a[j];
			}
			cout << endl;
		}
	}
}

求 n 累加和
模拟加法

#include"pch.h"
#include<cstdio>
using namespace std;
int a[10000];
int main()
{
	int n, l = 1, x;
	a[0] = 1;
	scanf_s("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		x = 0;
		for (int j = 0; j < l; j++)
		{
			if (j == 0)//第一位开始即其进位处理
			{
				a[j] = a[j] + i + x;
				x = a[j] / 10;
				a[j] = a[j] % 10;
			}
			else//对于第一位以后的进位处理
			{
				a[j] = a[j] + x;
				x = a[j] / 10;
				a[j] = a[j] % 10;
			}
		}
		if (x > 0)
		{
			a[l++] = x;
		}
	}
	while (a[l] == 0 && l >= 1)
		l--;
	for (int i = l; i >= 0; i--)
		printf("%d", a[i]);
}

P2818 天使的起誓
Tenshi非常幸运地被选为掌管智慧之匙的天使。在正式任职之前，她必须和其他新当选的天使一样要宣誓。

宣誓仪式是每位天使各自表述自己的使命，他们的发言稿放在n个呈圆形排列的宝盒中。这些宝盒按顺时针方向被编上号码1，2，…，n－1，n。

一开始天使们站在编号为n的宝盒旁。她们各自手上都有一个数字，代表她们自己的发言稿所在的盒子是从1号盒子开始按顺时针方向的第几个。例如：有7个盒子，如果Tenshi手上的数字为9，那么她的发言稿所在的盒子就是2个。现在天使们开始按照自己手上的数字来找发言稿，先找到的就可以先发言。

Tenshi一下子就找到了，于是她最先上台宣誓：“我将带领大家开启Noi之门……” Tenshi宣誓结束后，陆续有天使上台宣誓。可是有一位天使找了好久都找不到她的发言稿，原来她手上的数字m非常大，她转了好久都找不到她想找的宝盒。

请帮助这位天使找到她想找的宝盒编号。

输入格式
第一行为正整数n，第二行为正整数m，其中n,m满足2<=n<=10^8，2<=m<=101000

输出格式
只有一行（包括换行符），即天使想找的宝盒的编号。
很简单的一题，只需要m%n就可以了，但是m在10^1000次方内，所以只能用数组来存a[1000]，然后用同余方程求解，特判一下m%n==0就好了。
同余方程：1268 mod n=(((1%n10+2)%n10+6)%n*10+8)%n
另外补充几个常用的公式，很多问题都可以转化到这两个常用公式求解。

(a + b) % p = (a%p + b%p) %p
(a - b) % p = ((a%p - b%p) + p) %p
(a * b) % p = (a%p)*(b%p) %p

数论重要公式详解https://blog.csdn.net/deaidai/article/details/76474018

ac代码：

#include"pch.h"
#include<iostream>
#include<string>
using namespace std;
int a[1010];
string m;
int main()
{
	long long int n;
	cin >> n >> m;
	for (int i = 0; i < m.size(); i++) {
		a[i] = m[i] - 48;
	}
	int ans = 0;
	for (int i = 0; i < m.size(); i++) {
		ans = (ans * 10 + a[i]) % n;
	}
	if (ans == 0)
		cout << n << endl;
	else 
	cout << ans << endl;
}

题目描述
给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。

现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设A_n为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出A_n。
输入格式
一个正整数n，表示在AA柱上放有2n个圆盘。
输出格式
一个正整数, 为完成上述任务所需的最少移动次数A_n。

汉罗塔问题，不过就是变成双层的了，汉罗塔次数计算公式2^n-1，因为这里是双层，2 * ( 2 ^ n -1),因为n数据最大200，2 ^ 200 次方long long 存不住，用高精度存就好了。
ac代码：


#include<iostream>
using namespace std;
int a[300];
int count = 1;
int i, j;
long long int n;
void mul(int a[]) {
	int k = 0;
	for (int j = 0; j < count; j++) {
		int temp = 2 * a[j] + k;
		a[j] = temp % 10;
		k = temp / 10;
	}
	while (k) {
		a[count++] = k % 10;
		k /= 10;
	}
	
}
int main()
{
	a[0] = 1;
	cin >> n;
	for (i = 0; i < n; i++) {
		mul(a);
	}
	a[0]-=1; 
	for (j = 0; j <= i; j++) {
		if (a[j] != 0) {
			break;
		}
	}
	mul(a);
	for (int i = count - 1; i >= j; i--) {
		cout << a[i];
	}
}