OpenJudge 2737 大整数除法

链接地址：http://bailian.openjudge.cn/practice/2737/

题目：

总时间限制:

1000ms

内存限制:

65536kB
描述

求2个大的正整数相除的商

输入

第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符

输出

n行，每组测试数据有一行输出是相应的整数商

样例输入
3

2405337312963373359009260457742057439230496493930355595797660791082739646

2987192585318701752584429931160870372907079248971095012509790550883793197894

10000000000000000000000000000000000000000

10000000000

5409656775097850895687056798068970934546546575676768678435435345

1
样例输出
0

1000000000000000000000000000000

5409656775097850895687056798068970934546546575676768678435435345
提示

除法比较困难，建议大家最后做这题

思路：

套用大整数模板

代码：

 #include <iostream>

 #include <cstdio>

 #include <string>

 using namespace std;

 string sub(string s1,string s2)

 {

     int flag = ;

     if(s1.length()<s2.length() || (s1.length()==s2.length() && s1 < s2))

     {

         flag = ;

         string temp=s1;

         s1=s2;

         s2=temp;

     }

     int i,j;

     for(i=s1.length()-,j=s2.length()-;i>=;i--,j--)

     {

         s1[i]=char(s1[i]-(j>=?s2[j]-'':));   //注意细节

         if(s1[i]-''<)

         {

             s1[i]=char(s1[i] + );

             s1[i-]--;

         }

     }

     for(i = ; i < s1.length(); i++)

     {

         if(s1[i] != '') break;

     }

     if(i == s1.length()) i = s1.length()-;

     s1 = s1.substr(i);

     if(flag) s1 = "-" + s1;

     return s1;

 }

 string sum(string s1,string s2)

 {

     if(s1.length()<s2.length())

     {

         string temp=s1;

         s1=s2;

         s2=temp;

     }

     int i,j;

     for(i=s1.length()-,j=s2.length()-;i>=;i--,j--)

     {

         s1[i]=char(s1[i]+(j>=?s2[j]-'':));   //注意细节

         if(s1[i]-''>=)

         {

             s1[i]=char((s1[i]-'')%+'');

             if(i) s1[i-]++;

             else s1=''+s1;

         }

     }

     return s1;

 }

 string div(string s1,string s2)

 {

     string res = "";

     if(s1.length()<s2.length() || (s1.length()==s2.length() && s1 < s2))

     {

         return "";

     }

     int i;

     int sub_length = s1.length() - s2.length();

     for(i = sub_length; i >= ; i--)

     {

         string s3(i,'');

         string s4 = s2 + s3;

         do

         {

             string temp = sub(s1,s4);

             if(temp[] == '-') break;

             else

             {

                 s1 = temp;

                 res = sum(res,("" + s3));

             }

         }while();

     }

     return res;

 }

 int main()

 {

     int n;

     cin>>n;

     string str1,str2;

     while(n--)

     {

         cin>>str1>>str2;

         cout<<div(str1,str2)<<endl;

     }

     return ;

 }

巴特西

OpenJudge 2737 大整数除法

最新文章

热门文章