2^9 = 512 sum of its digits is 5 + 1 + 2 = 7 what is the sum of digits of number 2^N
Input Format
The first line contains an integer , i.e., number of test cases.
Next lines will contain an integer .
Output Format
Print the values corresponding to each test case.
Constraints
1<=T<=100
1<=N<=10000
แนวคิด
เนื่องจาก 2^N N สามารถมีค่ามากถึง 10000 ซึ่งไม่สามารถเก็บไว้ใน int หรือ long ได้ วิธีทำข้อนี้เราอาจจะใช้ Big Int เข้ามาช่วยหรือใช้ภาษาที่มี Big int ให้เรียกใช้ หรือไม่ก็ใช้แนวคิดการคูณเลขสมัยประถมเข้ามาแก้ก็ได้เหมือนกัน ในที่นี้ผมจะใช้วิธีการคูณเลขเข้ามาช่วย ผมสร้าง array ขนาดประมาณ5000 ช่องตัวนึงขึ้นมา array ตัวนี้จะเก็บผลคูณแต่ละหลัก โดนที่ array นี้จะเก็บจากหน้าไปหลัง เช่นถ้าเรามีเลข 128 array ของเราจะเก็บ [8,2,1,0,0,0,0,...] ทุกครั้งที่เราเอาเลข 2 ไปคูณแต่ละหลักค่าที่ได้อาจจะมากกว่า 10 หรือ น้อยกว่า 10 ก็ได้ แต่ในการคูณแต่ละหลักค่ามากสุดที่จะได้คือ 2*9 = 18 นั่นแสดงให้เห็นว่าเราจะได้ตัวเลข 2 ตัวคือตัว ทด กับ ตัวที่เป็นคำตอบของหลักนั้นๆ ถ้าคูณการในหลักแล้วได้ไม่ถึง 10 ตัวทดของเราก็จะเป็น 0 นั่นหมายความว่า ตัวทด = ผลคูณ/10 ส่วนคำตอบของหลัก = ผลคูณ % 10 นี่คือแนวคิด algorithm การคูณ แต่ว่าในการคูณแต่ละครั้งเราต้องคูณถึง 5000 รอบซึ่งถือว่าเสียเวลามาก ผมเลยหาว่าแต่ละรอบที่ 2 ยกกำลังมากขึ้นเรื่อยๆ จะมีกี่หลัก เพื่อที่จะทำให้ไวขึ้น โดยเราสามารถหาได้จาก จำนวนหลัก = (N*ln(2))/ln(10) และเพื่อทำให้โปรแกรมเราไวขึ้นเราสามารถเรียก N เป็น 10000 เพราะว่าเมื่อ N เป็น 10000 N ตั้งแต่ 1 ถึง 9999 ก็จะต้องถูกหาออกมาด้วย ในแต่ละรอบที่หา N มาได้ผมก็จะเก็บผลบวกไว้ลงไปใน array sum เหมือนเป็นการคิดคำตอบล่วงหน้าเอาไว้
สามารถเอาแนวคิดเขียนเป็นโค้ดได้แบบนี้
1<=T<=100
1<=N<=10000
แนวคิด
เนื่องจาก 2^N N สามารถมีค่ามากถึง 10000 ซึ่งไม่สามารถเก็บไว้ใน int หรือ long ได้ วิธีทำข้อนี้เราอาจจะใช้ Big Int เข้ามาช่วยหรือใช้ภาษาที่มี Big int ให้เรียกใช้ หรือไม่ก็ใช้แนวคิดการคูณเลขสมัยประถมเข้ามาแก้ก็ได้เหมือนกัน ในที่นี้ผมจะใช้วิธีการคูณเลขเข้ามาช่วย ผมสร้าง array ขนาดประมาณ5000 ช่องตัวนึงขึ้นมา array ตัวนี้จะเก็บผลคูณแต่ละหลัก โดนที่ array นี้จะเก็บจากหน้าไปหลัง เช่นถ้าเรามีเลข 128 array ของเราจะเก็บ [8,2,1,0,0,0,0,...] ทุกครั้งที่เราเอาเลข 2 ไปคูณแต่ละหลักค่าที่ได้อาจจะมากกว่า 10 หรือ น้อยกว่า 10 ก็ได้ แต่ในการคูณแต่ละหลักค่ามากสุดที่จะได้คือ 2*9 = 18 นั่นแสดงให้เห็นว่าเราจะได้ตัวเลข 2 ตัวคือตัว ทด กับ ตัวที่เป็นคำตอบของหลักนั้นๆ ถ้าคูณการในหลักแล้วได้ไม่ถึง 10 ตัวทดของเราก็จะเป็น 0 นั่นหมายความว่า ตัวทด = ผลคูณ/10 ส่วนคำตอบของหลัก = ผลคูณ % 10 นี่คือแนวคิด algorithm การคูณ แต่ว่าในการคูณแต่ละครั้งเราต้องคูณถึง 5000 รอบซึ่งถือว่าเสียเวลามาก ผมเลยหาว่าแต่ละรอบที่ 2 ยกกำลังมากขึ้นเรื่อยๆ จะมีกี่หลัก เพื่อที่จะทำให้ไวขึ้น โดยเราสามารถหาได้จาก จำนวนหลัก = (N*ln(2))/ln(10) และเพื่อทำให้โปรแกรมเราไวขึ้นเราสามารถเรียก N เป็น 10000 เพราะว่าเมื่อ N เป็น 10000 N ตั้งแต่ 1 ถึง 9999 ก็จะต้องถูกหาออกมาด้วย ในแต่ละรอบที่หา N มาได้ผมก็จะเก็บผลบวกไว้ลงไปใน array sum เหมือนเป็นการคิดคำตอบล่วงหน้าเอาไว้
สามารถเอาแนวคิดเขียนเป็นโค้ดได้แบบนี้
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <iomanip> | |
#include <cstring> | |
#include <cmath> | |
using namespace std; | |
typedef long long ll; | |
int main() | |
{ | |
int sum[10002] = {0}; | |
int arr[5000] = {0}; | |
sum[1] = 2; | |
arr[0] = 2; | |
for(int i = 2;i<=10005;i++) | |
{ | |
int itr = 0; | |
int carry = 0; | |
int k = ceil((i*log(2))/log(10)); | |
while(itr<=k) | |
{ | |
int product = arr[itr] * 2; | |
int digit = product % 10; | |
arr[itr] = digit + carry; | |
carry = product / 10; | |
itr++; | |
} | |
arr[itr] += carry; | |
for(int j = 0;j<=k;j++) | |
sum[i] += arr[j]; | |
} | |
int tc; | |
cin >> tc; | |
while(tc-- > 0) | |
{ | |
int n; | |
cin >> n; | |
cout << sum[n] << endl; | |
} | |
} |
ไม่มีความคิดเห็น:
แสดงความคิดเห็น