这题得用高精度!!!!!AC了,发个代码,用得上的给个赞吧

#include<iostream>

#include<algorithm>

using namespace std;

const int L=10005;

string mul(string a,string b)

{

string s;

int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();
fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';

for(int i=1;i<=La;i++)

for(int j=1;j<=Lb;j++)

nc[i+j-1]+=na[i]*nb[j];
for(int i=1;i<=La+Lb;i++)

nc[i+1]+=nc[i]/10,nc[i]%=10;

if(nc[La+Lb]) s+=nc[La+Lb]+'0';
for(int i=La+Lb-1;i>=1;i--)

s+=nc[i]+'0';
return s;

}

int sub(int *a,int *b,int La,int Lb)

{

if(La<Lb) return -1;
if(La==Lb)
{
for(int i=La-1;i>=0;i--)

if(a[i]>b[i]) break;

else if(a[i]<b[i]) return -1;

}

for(int i=0;i<La;i++)
{
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1;i>=0;i--)

if(a[i]) return i+1;
return 0;

}

string div(string n1,string n2,int nn)
{

string s,v;
int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);
for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';

for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';

if(La<Lb || (La==Lb && n1<n2)) {cout<<0<<endl;return n1;}
int t=La-Lb;
for(int i=La-1;i>=0;i--)
if(i>=t) b[i]=b[i-t];

else b[i]=0;

Lb=La;

for(int j=0;j<=t;j++)

{

int temp;

while((temp=sub(a,b+j,La,Lb-j))>=0)
{

La=temp;

r[t-j]++;

}

}

for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;
while(!r[i]) i--;
while(i>=0) s+=r[i--]+'0';

//cout<<s<<endl;
i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';

if(v.empty()) v="0";

//cout<<v<<endl;
if(nn==1) return s;
if(nn==2) return v;
}
bool judge(string s)
{
for(int i=0;i<s.size();i++)
if(s[i]!='0') return false;
return true;
}
string gcd(string a,string b)
{
string t;
while(!judge(b))
{
t=a;
a=b;
b=div(t,b,2);
}
return a;
}
int main()
{
string a,b;
while(cin>>a>>b)

{

if(a.size()<b.size() || (a.size()==b.size() && a<b))
{

string t=a;

a=b;

b=t;

}

// cout<<gcd(a,b)<<endl;

cout<<div(mul(a,b),gcd(a,b),1)<<endl;
}

//system("pause");
return 0;

}

4 条评论

  • @ 2015-08-19 12:43:58

    不用高精度我真不知道100位怎么做

  • @ 2015-06-22 12:09:26

    ##赞~(≧▽≦)/~##
    神代码
    ###very good
    #include<iostream>

    include<algorithm>
    using namespace std;
    const int L=10005;
    string mul(string a,string b)
    {
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
    for(int j=1;j<=Lb;j++)
    nc[i+j-1]+=na[i]nb[j];
    for(int i=1;i<=La+Lb;i++)
    nc[i+1]+=nc[i]/10,nc[i]%=10;
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';
    for(int i=La+Lb-1;i>=1;i--)
    s+=nc[i]+'0';
    return s;
    }
    int sub(int a,int *b,int La,int Lb)
    {
    if(La<Lb) return -1; if(La==Lb) { for(int i=La-1;i>=0;i--)
    if(a[i]>b[i]) break;
    else if(a[i]<b[i]) return -1;
    }
    for(int i=0;i<La;i++)
    {
    a[i]-=b[i];
    if(a[i]<0) a[i]+=10,a[i+1]--;
    }
    for(int i=La-1;i>=0;i--)

    if(a[i]) return i+1;
    return 0;
    }
    string div(string n1,string n2,int nn)
    {
    string s,v;
    int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
    fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);
    for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
    for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
    if(La<Lb || (La==Lb && n1<n2)) {cout<<0<<endl;return n1;} int t=La-Lb; for(int i=La-1;i>=0;i--)
    if(i>=t) b[i]=b[i-t];
    else b[i]=0;
    Lb=La;
    for(int j=0;j<=t;j++)
    {
    int temp;
    while((temp=sub(a,b+j,La,Lb-j))>=0)
    {
    La=temp;
    r[t-j]++;
    }
    }
    for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10; while(!r[i]) i--; while(i>=0) s+=r[i--]+'0';
    //cout<<s<<endl; i=tp; while(!a[i]) i--; while(i>=0) v+=a[i--]+'0';
    if(v.empty()) v="0";
    //cout<<v<<endl; if(nn==1) return s; if(nn==2) return v; } bool judge(string s) { for(int i=0;i<s.size();i++) if(s[i]!='0') return false; return true; } string gcd(string a,string b) { string t; while(!judge(b)) { t=a; a=b; b=div(t,b,2); } return a; } int main() { string a,b; while(cin>>a>>b)
    {
    if(a.size()<b.size() || (a.size()==b.size() && a<b))
    {
    string t=a;
    a=b;
    b=t;
    }
    // cout<<gcd(a,b)<<endl;
    cout<<div(mul(a,b),gcd(a,b),1)<<endl;
    }
    //system("pause");
    return 0;
    }

  • @ 2015-03-15 10:24:39

    赞(看不懂

  • @ 2014-12-17 13:46:16

    真是的,10^100也搞得出来

  • 1

信息

ID
1047
难度
8
分类
高精度 点击显示
标签
(无)
递交数
7167
已通过
742
通过率
10%
被复制
11
上传者