Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CP - Số chính phương

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/cp


John là một người rất đam mê toán học, một lần cậu viết ra một dãy số các chữ số và nhận ra rằng dãy số vừa viết có thể tách thành một số đoạn con liên tiếp, mà mỗi đoạn con tạo thành một số là số chính phương.
Ví dụ: dãy số 149 có thể tách thành 3 đoạn: 1, 4, 9 -> mỗi đoạn đều là số chính phương hoặc có thể tách thành 2 đoạn 1 và 49.
John muốn biết là có bao nhiêu cách tách khác nhau (hai cách tách được gọi là khác nhau nếu tồn tại một vị trí tách khác nhau) dãy chữ số mình vừa viết. Điều kiện là các đoạn tách ra không bắt đầu bằng chữ số 0.

Input

- Dòng đầu là số lượng test: nTest.
- nTest dòng tiếp theo mỗi dòng ghi ra dãy chữ số mà John viết (độ dài không quá 100).

Output

- Với mỗi test ghi ra số lượng cách tìm được trên 1 dòng.

Example

Input:
1
169

Output:
2
169 -> 169 = 13^2
169 -> 16 = 4^2 và 9 = 3^2.

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-14
Thời gian chạy:1.370s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP C99 JAVA NICE PAS-GPC PAS-FPC

hide comments
2019-08-14 21:19:19
Giải quyết dễ dàng bằng QHĐ nếu kiểm tra được một số lớn (100 chữ số) có phải số chính phương không.

Nhận xét rằng với một modulo X bất kỳ thì tập giá trị của biểu thức (T^2 mod X) có lực lượng <= X/2+1. Do đó ta có thể random X, sau đó kiểm tra số nhập vào mod X có nằm trong tập trên ko. Nếu ko thì chắc chắn ko phải số cp, nếu có thì có thể. Chỉ cần thực hiện 20 lần thì tỉ lệ sai đã là 1/2^20 (đủ để AC bài này).

Code: ideone.com/rDMGHj

Last edit: 2019-08-14 21:20:19
2019-03-11 16:02:55
cho em xin code với
2018-08-06 04:20:55
xin test sai
2013-03-12 15:16:26 Bùi Vãn Quãng



2012-11-28 18:11:44 2ez
time chặt quá!!
2011-12-13 03:04:42 Bui Duy Thong
test 10 ra 0 ma
do tach ra thi phai tat ca cac so nhan dc deu la chinh phuong het
2011-12-13 03:03:40 Bui Duy Thong
the ca 100 chu so ay la 1 so chinh phuong thi giai quyet the nao???:(
2011-06-29 06:15:26 pitago
Test 1
10
ra 0 hay 1 vậy?
2009-04-10 16:36:05 dhkhtn
kq la so int64
2009-04-10 16:33:39 dhkhtn
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.