[Thuật toán] Tính bình phương của 1 số gồm n số 1

Đề bài:

Cho số S = 111…11 (n chữ số 1, hệ thập phân), tính S^2.
Input
– Dòng đầu tiên: số lượng test k (k<=40).
– k dòng tiếp, mỗi dòng ghi số n – số lượng chữ số 1 của S. (1 <= n <= 1000000)
Output
– Với mỗi test ghi kết quả trên 1 dòng.
Example
Input:
2
1
2
Output:
1
121

Cách giải:
Ta thấy KQ có dạng đối xứng 123…n…321. VD n=3 thì 111^2 = 12321
Nhưng nhận thấy với n =10 thì dạng đối xứng này có vẻ không đúng lắm.
VD: với n = 13 tức là ta có 1111111111111^2.

            1111111111111
           1111111111111
          1111111111111
         1111111111111
+       1111111111111
       1111111111111
      1111111111111
     1111111111111
    1111111111111
   1111111111111
  1111111111111
 1111111111111
1111111111111
=========================
1234567901234320987654321

Chúng ta thấy quy luật đối xứng không còn nữa. Và mình nảy ra một ý định đó là thế này. Ta cứ viết như đối xứng đi, rồi thực hiện như sau:

Ta sẽ thực hiện in từng số từ phải sang trái và ta có code sau:

#include <iostream>
#include <string>
using namespace std;
int main()
{
		int k, n;

		cin>>k;
		for (int i=0; i<k; i++)
		{
			cin>>n;
			string s = "";
			int temp = 0;	// temp la phan du khi chi so cho 10. VD 13 thi temp la 1.
			int j = 1, ji = 1;
			// bat dau viet tu phai sang trai
			while (j>0)
			{
				// cong tung cap nhu hinh ((j+temp)%10)
				//sau do chen vao giua
				s.insert(0, 1, (char)((j+temp)%10+'0')); 
				temp = (j+temp)/10;
				if (j==n) ji = -1;	// quay nguoc lai khi du n so
				j += ji;
			}
		cout<<s<<endl;
		}
	return 0;
}

Sau khi có code trên, xuất một số KQ thì rút ra quy luật như sau:
Dãy số chia làm 3 phần phần đầu có cấu trúc như sau :
+/ phần đầu: 123456790123456790123456790… tức là lặp lại của đoạn 123456790 (n-1)/9 = n1 lần.
+ phần giữa: 123…x…32 với x = n – 9*n1.
+/ phần cuối: lặp n1 lần 098765432 và có số 1 ở cuối cùng. Để đơn giản ta cứ cho phần giữa là đối xứng tức là có dạng 12321 rồi ta chèn phần cuối vào trước số 1 ở cuối.

#include <iostream>
#include <string>
using namespace std;
int main()
{
	int k, n;
	
	cin>>k;
	for (int i=0; i<k; i++)
	{
		cin>>n;
		string s = "", s1 = "123456790", s2 = "098765432";
		int n1 = (n-1)/9, n2 = n - 9*n1;
		
		// doan giua
		for (int i=1; i<=n2; i++)
			s.insert(s.length(), 1, (char)(i + '0'));
			
		for (int i=n2-1; i>0; i--)
			s.insert(s.length(), 1, (char)(i + '0'));
		
		// neu n tu 10 tro len
		if (n>9)
		{
			// doan dau
			for (int i=0; i<n1; i++)
				s.insert(0, s1);
			// doan cuoi
			for (int i=0; i<n1; i++)
				s.insert(s.length()-1, s2);
		}
		cout<<s<<endl;
	}
	return 0;
}

Minh họa KQ khi nhập k =13 và 5 số n (14, 37, 30, 113, 352) tuơng ứng như trong hình.