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

描述

刚结束了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";

}

【noip模拟赛10】奇怪的贸易 高精度的相关教程结束。