Tính nhanh bình phương của một số có n chữ số 1, với n <= 1triệu

[troinau]

Đề bài :
Mình dùng 2 vòng for lòng nhau để tính, nhưng kết quả khi test trên http://www.spoj.pl là chạy chậm. Có cách nào để tính nhanh kết quả khi tính bình phương ?

Cho số S = 111...11 (n chữ số 1, hệ thập phân), tính S2.

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

code của mình

void Nhan(long n)
{
	long *a = new long[MAX];
	long *b = new long[MAX];
	for(long i=0; i<n; i++)
		a[i] = 1;
	for(long i=0; i<n*2-1; i++)
		b[i] = 0;
	for(long i=0; i<n; i++)
	{
		int d=0, sum =0;
		for(long j=0; j<n; j++)
		{
			sum = b[i+j] + a[j] + d;
			if(sum > 9)
			{
				d=sum / 10;
				sum = sum % 10;				
			}
			else
			{
				d=0;
			}
			b[i + j] = sum;
		}
	}
	
}

[doicanhden]

Tìm quy luật của số kết quả xem:

     1 * 1      =      1    11 * 11     =     121   111 * 111    =    12321  1111 * 1111   =   1234321 11111 * 11111  =  123454321111111 * 111111 = 12345654321   11 *  11 ___ 1111___121    111  *   111   ___  111 111111______12321      1111    *     1111     ___    1111   1111  1111 1111_______1234321

[troinau]

mình thấy qui luật đến 9 thôi, qua 10 là hết rồi
vd:
8: => 123456787654321
9 = > 12345678987654321
nhưng
10: => 1234567900987654321
12: => 12345679012320987654321

[noone2407]

Tui thấy tuy qua 9 nó vẫn có quy luật riêng, và số dài bao nhiêu đi nữa nó vẫn có quy luật, và hàm giải ở đây chỉ cần 1 hàm cộng chuỗi là đủ

[langman]

[void Nhan(long n)
{
long *a = new long[MAX];
long *b = new long[MAX];
for(long i=0; i<n; i++)
a[i] = 1;
for(long i=0; i<n*2-1; i++)
b[i] = 0;
for(long i=0; i<n; i++)
{
int d=0, sum =0;
for(long j=0; j<n; j++)
{
sum = b[i+j] + a[j] + d;
if(sum > 9)
{
d=sum / 10;
sum = sum % 10;
}
else
{
d=0;
}
b[i + j] = sum;
}
}

}

Code của bạn hơi thô sơ, nhập 1 triệu vào ko bít có sống ko?

[Sounj]

Code của bạn hơi thô sơ, nhập 1 triệu vào ko bít có sống ko?

O(n^2), sống bằng niềm tin :((

Chủ thớt làm theo hướng này xem sao
VD nhé : tính 111111^2:
111111 * 111111 = (111000 + 111)*(111000 + 111) = 111000*111000 + 2*111000*111 + 111*111
= 111*111* 1000000 + 2 * 111 * 111 * 1000 + 111*111
=> Ta đã hạ cấp từ phép bình phương số có 6 chữ số xuống phép bình phương số có 3 chữ số.

Trường hợp số chữ số là số lẻ thì có thể làm thế này, hạ nó xuống 1 cấp:
(11111*11111) = (10000+1111)*(10000+1111)

=> Thuật toán : Nếu n nhận vào quá lớn thì áp dụng thuật toán để chuyển xuống tính với n/2, n/4 ....v...v... cho đến khi n là đủ nhỏ để có thể tính đc, hoặc đơn giản nhất là chỉ dừng lại khi n<10
Có thể thấy là thuật toán có độ phức tạp tỷ lệ với n log2(n)

[hunterphu]

http://vn.spoj.com/problems/MULONE/
Bài này chỉ print thôi mà

[Sounj]

http://vn.spoj.com/problems/MULONE/
Bài này chỉ print thôi mà

print thế nào cậu bày giúp với Từ 10 trở lên, mình nhìn chả thấy nó có cái qui luật gì sất => chỉ biết làm cách chia đôi chiều dài của nó rồi tính tiếp

[kimlama]

Mình search được công thức + mã nguồn . Và dưới đây là công thức đó. Hy vọng giúp được chủ thớt.

{ 11..1^2 (n chso1)=(99..9/9)^2=((10^n-1)/9)^2                   = (10^2n-2*10^n+1)/81                            =  99..980001 /81                  ( n-1 chso 9, n-1 chso 0 )                                                   }

[Sounj]

Mình search được công thức + mã nguồn . Và dưới đây là công thức đó. Hy vọng giúp được chủ thớt.

{ 11..1^2 (n chso1)=(99..9/9)^2=((10^n-1)/9)^2                   = (10^2n-2*10^n+1)/81                            =  99..980001 /81                  ( n-1 chso 9, n-1 chso 0 )                                                   }

Ra vậy, hóa ra là phải nhân nó với 9. Túm lại là phải ngồi thực hiện 1 phép chia số lớn. Cái này thì đúng là O(n) rồi
Mấy cậu cứ biểu là có qui luật, có qui luật, nhưng nhìn vào mấy cái kết quả muốn mờ mắt luôn mà có cái qui luật nào đâu