Ước chung của chuỗi

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Một chuỗi \(a\) được gọi là ước của chuỗi \(b\) nếu tồn tại một số nguyên dương \(x\) sao cho khi ta viết \(x\) lần chuỗi \(a\) thì sẽ thu được chuỗi \(b\).

Ví dụ chuỗi abab có 2 ước là ab và abab.

Yêu cầu: Bạn được cho 2 chuỗi \(S_1\) và \(S_2\), hãy đếm xem chúng có tất cả bao nhiêu ước chung?

Input

Dòng đầu tiên chứa chuỗi \(S_1\).
Dòng thứ hai chứa chuỗi \(S_2\).
Cả 2 chuỗi đều gồm các chữ cái thường, độ dài 2 chuỗi không quá \(10^5\) ký tự.

Output

In ra một số nguyên là kết quả của bài toán.

Example

Test 1

Input

xyztxyzt  
xyzt

Output

Note

Chuỗi xyztxyzt có 2 chuỗi ước là: xyzt và xyztxyzt; Chuỗi xyzt có 1 chuỗi ước là: xyzt nên có 1 chuỗi ước chung là xyzt

Test 2

Input

aaaa
aa

Output

Note

Chuỗi aaaa có 3 chuỗi ước là: a, aa và aaaa; Chuỗi aa có 2 chuỗi ước là: a và aa nên có 2 chuỗi ước chung là a và aa

Bình luận

bruh python code trick

a = input()
b = input()
len_a = len(a)
len_b = len(b)
res = 0
for i in range(1,len_a + 1):
    if len_a % i == 0 and len_b % i == 0:
        k = a[:i]
        if a.replace(k,'') == '' and b.replace(k,'') == '':
            res += 1
print(res)

Phản hồi

hoquyanhnho • 9:28 a.m. 22 Tháng 12, 2022 •

var
s,st,sm,s1,tg:ansistring;
i,d:longint;
begin
readln(s);
readln(st);
while ( ( s[1]=' ' )) do delete(s,1,1);
while ( s[length(s)]=' ' ) do delete(s,length(s),1);
while ( pos(#32#32,s) > 0 ) do delete(s,pos(#32#32,s),1);
while ( ( st[1]=' ' )) do delete(st,1,1);
while ( st[length(st)]=' ' ) do delete(st,length(st),1);
while ( pos(#32#32,st) > 0 ) do delete(st,pos(#32#32,st),1);
if ( length(s) > length(st) )then
begin
tg:=s;
s:=st;
st:=tg;
end;
d:=0;
for i:=1 to length(s) do
begin
if ( length(st) mod i= 0) then
begin
s1:=copy(s,1,i);
sm:='';
while ( length(sm)<length(s)) do sm:=sm+s1;
if ( sm=s) then inc(d);
end;
end;
writeln(d);
end.

-2
Phản hồi Chia sẻ

Lê_Gia_Khánh • 11:02 p.m. 14 Tháng 5, 2020 •

Sai chính tả tè le kìa thầy :))

This comment is hidden due to too much negative feedback. Click here to view it.

-37
Phản hồi Chia sẻ

1 phản hồi