高精度

[TOC]

高精度

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[100000],c[100000],la,lb,lc;
//1.字符串读入
//2.字符串转数组
//3.竖式加法
//4.消前导0
//5.倒序输出
int main(){
cin>>x>>y;
la = x.length();
lb = y.length();
for(int i=0;i<la;i++){
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++){
b[lb-i]=y[i]-'0';
}
lc = max(la,lb);
for(int i=1;i<=lc;i++){
c[i]+=a[i]+b[i];
c[i+1] = c[i]/10;
c[i] %= 10;
}
if(c[lc+1]>0) lc++;
for(int i=lc;i>=1;i--)
cout<<c[i];
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;
string x,y;
int a[100005],b[100005],c[100005],la,lb;
int main(){
cin>>x>>y;
la = x.length();
lb = y.length();
if(la<lb||la==lb&&x<y){
swap(x,y);
swap(la,lb);
cout<<'-';
}
for(int i=0;i<la;i++)
a[la-i] = x[i] - '0';

for(int i=0;i<lb;i++)
b[lb-i] = y[i] - '0';

for(int i=1;i<=la;i++){
if(a[i]<b[i]){
a[i]+=10;
a[i+1]--;
}
c[i]=a[i]-b[i];
}
while(c[la]==0&&la>1)
la--;
for(int i=la;i>=1;i--)
cout<<c[i];
return 0;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
string x,y;
int a[100005],b[100005],c[100005],la,lb,lc;
int main(){
cin>>x>>y;
la = x.length();
lb = y.length();
for(int i=0;i<la;i++){
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++){
b[lb-i]=y[i]-'0';
}
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++){
c[i+j-1] += a[i]*b[j];
c[i+j] += c[i+j-1] / 10;
c[i+j-1] %= 10;
}
}
lc = la+lb;
while(c[lc]==0&&lc>1){
lc--;
}
for(int i=lc;i>=1;i--){
cout<<c[i];
}
return 0;
}

B进制星球

原文题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
string x,y;
int a[100005],b[100005],c[100005],la,lb,lc;
int main(){
cin>>n>>x>>y;
la = x.length;
lb = y.length;
for(int i=0;i<la;i++){
if(x[i]>='A')
a[la-i]=x[i]-'A'+10;
else
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++){
if(y[i]>='A')
b[lb-i]=y[i]-'A'+10;
else
b[lb-i]=y[i]-'0';
}
lc = max(la,lb);
for(int i=1;i<=lc;i++){
c[i]+=a[i]+b[i];
//c[i+1]+=c[i]/10;
c[i+1]+=c[i]/n;
//c[i]%=10;
c[i]%=n;
}
if(c[lc+1]>0)lc++;
for(int i=lc;i>=1;i--){
if(c[i]>=10)
cout>>char(c[i]-10+'A');
else
cout>>c[i];
}
return 0;
}

求余操作

题目描述

给你三个整数 b,p,k,求 b^p mod k。

输入格式

一行三个整数 b,p,kb,p,k

输出格式

输出 b^p mod k=s

s 为运算结果

输入 #1

1
2 10 9

输出 #1

1
2^10 mod 9=7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
long long a,b,c;
cin>>a>>b>>c;
cout<<a<<"^"<<b<<" mod "<<c<<"=";
int res = 1;
while(b){
if(b&1){
res = res*a%c;
}
b>>=1;
a = a*a%c;
}
cout<<res%c<<endl;
}

迫害

题目原文
题目描述

有 k个人,X 要对这 k 个人进行迫害。这 k 个人,每一个人都拥有一个数字,分别从 1 至 k。X 拥有 n+m 个数字,这些数字为 n 个 1 和 m 个大小可由 X 决定的数字(每个数字定好之后不能更换)。X 能对这些人进行迫害,当且仅当他能用手中若干个数的加和等于被迫害人的数字,一次迫害就成功了(不会消耗数字)。

由于 X 的权利极大,又十分邪恶,他想要从第 11 个人开始一个一个进行迫害行动。由于小 Z 也在这个被迫害的行列里,他十分的慌张,希望你来告诉他 X 能最多能从第一个人开始连续迫害多少个人。由于被迫害的人太多了,所以请将答案对 1000000007 取模。

输入格式

第一行两个整数 n,m,表示 X 有 n个 1,有 m 个大小可自定的数。

输出格式

请你告诉小 Z,X 能迫害多少个人。

输入 #1

1
1 2

输出 #1

1
7

输入 #2

1
2 2

输出 #2

1
11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*题目是有规律的,答案是(n+1)(2^m-1)+n*/
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
f(n1,n2);
}
public static void f(int n,int m){
if(m==0){
System.out.println(n);
return ;
}
if(m==1){
System.out.println((2*n+1)%1000000007);
return ;
}
long tmp=2;//底数
long sum=1;
//求出2^m,快速幂
while(m!=0){
if((m&1)==1){
sum *= tmp;
sum%=1000000007;
}
tmp = (tmp*tmp)%1000000007;//tmp也需要%,否则可能会超出范围
m = m>>1;
}
sum = (sum-1)*(n+1)+n;
sum%=1000000007;
System.out.println(sum);
}
}