【noip模拟赛10】奇怪的贸易 高精度

时间:2021-05-29 11:56:51

描述

刚结束了CS战斗的小D又进入了EVE的游戏世界,在游戏中小D是一名商人,每天要做的事情就是在这里买东西,再运到那里去卖。这次小D来到了陌生的X星,X星上有n种货物,小D决定每种都买走一些,他用ai来表示第i种货物购买的数量,X星人对物品的单价有特别的决定方式。他们首先会选择一个基本价x,第一种物品单价为x,第二种物品单价为x2,第三种物品单价为x3……第i种物品单价为xi.结算总价时,你还需要给他们一笔手续费a0,小D不知道自己带的钱是否能够进行这笔交易,所以请你帮助他计算这笔交易他要支付的总金额是多少。

输入

x  n

a0

a1

a2

.

.

.

an

第一行两个数分别表示基准价x (x<=10),物品种数n (n<=100000)

第二行一个数,手续费a0 (a0<=100)

接下来的n行每行一个数,第i行表示第i种物品购买的数量(ai<=100)

输出

输出结果的最后100位,若不足100位请高位用零补足

输入样例 1

2 3
4
3
2
1

输出样例 1

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026

提示

【数据规模】对20%的数据:n<=10 对50%的数据:n<=200 对100%的数据:n<=100000

就是模拟高精度:

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 1000+50 int n,m;
int a[N],b[N],c[N]; int mul(int t)
{
int k,g=;
rep(i,,)
{
k=b[i]*n+g;
b[i]=k%;
g=k/;
}
g=;
rep(i,,)
{
k=b[i]*t+g;
c[i]=k%;
g=k/;
}
}
int add()
{
int k,g=;
rep(i,,)
{
k=c[i]+a[i]+g;
a[i]=k%;
g=k/;
}
} int main()
{
int k;
RIII(n,m,k);
b[]=;
int x=k,y=;
while(x)
{
a[y]=x%;
x/=;
y++;
}
rep(i,,m)
{
CLR(c,);
int x;
RI(x);
mul(x);
add();
}
repp(i,,)
printf("%d",a[i]); return ;
}

附上全部的高精度

#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
//compare比较函数:相等返回0,大于返回1,小于返回-1
int compare(string str1,string str2)
{
if(str1.length()>str2.length()) return ;
else if(str1.length()<str2.length()) return -;
else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
string add(string str1,string str2)//高精度加法
{
string str;
int len1=str1.length();
int len2=str2.length();
//前面补0,弄成长度相同
if(len1<len2)
{
for(int i=;i<=len2-len1;i++)
str1=""+str1;
}
else
{
for(int i=;i<=len1-len2;i++)
str2=""+str2;
}
len1=str1.length();
int cf=;
int temp;
for(int i=len1-;i>=;i--)
{
temp=str1[i]-''+str2[i]-''+cf;
cf=temp/;
temp%=;
str=char(temp+'')+str;
}
if(cf!=) str=char(cf+'')+str;
return str;
}
//高精度减法
//只能是两个正数相减,而且要大减小
/*string sub(string str1,string str2)//高精度减法
{
string str;
int tmp=str1.length()-str2.length();
int cf=0;
for(int i=str2.length()-1;i>=0;i--)
{
if(str1[tmp+i]<str2[i]+cf)
{
str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
cf=1;
}
else
{
str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
cf=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(str1[i]-cf>='0')
{
str=char(str1[i]-cf)+str;
cf=0;
}
else
{
str=char(str1[i]-cf+10)+str;
cf=1;
}
}
str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
return str;
}
//高精度乘法
//只能是两个正数相乘
string mul(string str1,string str2)
{
string str;
int len1=str1.length();
int len2=str2.length();
string tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr="";
int temp=str2[i]-'0';
int t=0;
int cf=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(str1[j]-'0')+cf)%10;
cf=(temp*(str1[j]-'0')+cf)/10;
tempstr=char(t+'0')+tempstr;
}
if(cf!=0) tempstr=char(cf+'0')+tempstr;
}
str=add(str,tempstr);
}
str.erase(0,str.find_first_not_of('0'));
return str;
}
//高精度除法
//两个正数相除,商为quotient,余数为residue
//需要高精度减法和乘法
void div(string str1,string str2,string &quotient,string &residue)
{
quotient=residue="";//清空
if(str2=="0")//判断除数是否为0
{
quotient=residue="ERROR";
return;
}
if(str1=="0")//判断被除数是否为0
{
quotient=residue="0";
return;
}
int res=compare(str1,str2);
if(res<0)
{
quotient="0";
residue=str1;
return;
}
else if(res==0)
{
quotient="1";
residue="0";
return;
}
else
{
int len1=str1.length();
int len2=str2.length();
string tempstr;
tempstr.append(str1,0,len2-1);
for(int i=len2-1;i<len1;i++)
{
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty())
tempstr="0";
for(char ch='9';ch>='0';ch--)//试商
{
string str,tmp;
str=str+ch;
tmp=mul(str2,str);
if(compare(tmp,tempstr)<=0)//试商成功
{
quotient=quotient+ch;
tempstr=sub(tempstr,tmp);
break;
}
}
}
residue=tempstr;
}
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()) quotient="0";
}