Link Sub: https://www.spoj.com/PTIT/problems/BCPOW/
Người Gửi: Dương Lee
- Problem:
Cho hai số n, m nguyên dương (n,m<=200). Hỏi trong biểu diễn thập phân của tổng S=2n+3m chữ số Cho hai số n, m nguyên dương (n,m<=200). Hỏi trong biểu diễn thập phân của tổng S=2^n+3^m chữ số đầu tiên là chữ số nào?
Ví dụ :
với n=4 , m=2 thì S=25 có chữ số đầu tiên là 2.
Với n=8, m=4 thì s=337 có chữ số đầu là 3.
InputVí dụ :
với n=4 , m=2 thì S=25 có chữ số đầu tiên là 2.
Với n=8, m=4 thì s=337 có chữ số đầu là 3.
Dữ liệu vào gồm một dòng duy nhất ghi 2 số n, m cách nhau bởi dấu cách.
Output
Example:
Một số duy nhất là đáp số của bài toán.
Input
4 2
Output:
2
Input
8 4
Output:
3
- Solution:
Input
8 4
Output:
3
- n, m <= 200 nên sẽ phải dùng số nguyên lớn để xử lý (cộng string)
- Code dưới đây chia làm 2 phần: Công số nguyên lớn và Lũy thừa số nguyên lớn.
+ Cong: Để cộng hai string như một số thì ta phải quy nó về cùng chiều dài số lơn nhất, sau đó áp dụng quy tắt cộng và nhớ số từ cuối lên đầu.
VD:
a = "123"
b = "4567"
->
a = "0123"
b = "4567"
<- "+", rs = "" , remember = 0
3 + 7 + 0 = 10 -> rs = "0" remember = 1
2 + 6 + 1 = 9 -> rs = "90" remember = 0
1 + 5 + 0 = 6 -> rs = "690" remember = 0
0 + 4 + 0 = 4 -> rs = "4690" remember = 0
+ Luythua: đối với luy thừa thì thực chất ta cộng nhiều số lại với nhau thôi.
VD: 2^3 = 2*2*2
-> rs = "2"
rs = rs*2
-> rs = Cong(rs, rs) = 4
rs = rs*2
-> rs = Cong(rs, rs) = 8
- Code dưới đây chia làm 2 phần: Công số nguyên lớn và Lũy thừa số nguyên lớn.
+ Cong: Để cộng hai string như một số thì ta phải quy nó về cùng chiều dài số lơn nhất, sau đó áp dụng quy tắt cộng và nhớ số từ cuối lên đầu.
VD:
a = "123"
b = "4567"
->
a = "0123"
b = "4567"
<- "+", rs = "" , remember = 0
3 + 7 + 0 = 10 -> rs = "0" remember = 1
2 + 6 + 1 = 9 -> rs = "90" remember = 0
1 + 5 + 0 = 6 -> rs = "690" remember = 0
0 + 4 + 0 = 4 -> rs = "4690" remember = 0
+ Luythua: đối với luy thừa thì thực chất ta cộng nhiều số lại với nhau thôi.
VD: 2^3 = 2*2*2
-> rs = "2"
rs = rs*2
-> rs = Cong(rs, rs) = 4
rs = rs*2
-> rs = Cong(rs, rs) = 8
- Code:
C++:
https://ideone.com/fYJSFb
#include <iostream>
#include <math.h>
using namespace std;
string Cong(string a, string b)
{
int len = max(a.length(), b.length());
while (a.length()<len)
a="0"+a;
while (b.length()<len)
b="0"+b;
/*
a = 123
b = 4567
->
a = 0123
b = 4567
*/
string rs = "";
int remember = 0;
for (int i=len-1; i>=0; i--)
{
int n1 = a[i]-'0';
int n2 = b[i]-'0';
int s = n1+n2+remember;
char rs_tmp = s%10 + '0';
rs = rs_tmp + rs;
remember = s/10;
}
if (remember!=0)
return char(remember+'0')+rs;
return rs;
}
string luythua(string x, int n, int d)
{
if (n==0) return "1";
else if (n==1) return x;
string rs = x;
for (int i=2; i<=n; i++)
{
string rs_tmp = rs;
for (int j=2; j<=d; j++)
{
rs = Cong(rs, rs_tmp); //2^3 = ((2)*2)*2 = ((2)+(2))+((2)+(2))
}
}
return rs;
}
int main()
{
int n, m;
cin>>n>>m;
string lt2 = luythua("2", n, 2);
string lt3 = luythua("3", m, 3);
string S = Cong(lt2, lt3);
cout<<S[0];
return 0;
}JAVA:
...Python:
...