[CF490C] HACKING CYPHER, P151PROF spoj Cipher

Tên bài toán: Hacking Cypher

Nguồn: Codefores Round #279 Div. 2 – Problem C

Đề bài http://codeforces.com/problemset/problem/490/C

1. Đề bài CF490C codeforces

Mô tả bài toán:

Cho một số xâu ký tự biểu diễn một số cực lớn và 2 số tự nhiên a và b.

Tách xâu ký tự thành hai phần, phần bên trái chia cho a, phần bên phải chia cho b.

Liệu có tách xâu đó để cho phần bên trái chia hết cho a và phần bên phải chia hết cho b.

Yêu cầu: Xác định khả năng tách xâu chữ số cho trước thành 2 phần, phần bên trái chia hết cho a, phần bên phải chia hết cho b. In ra trường hợp tách được đó với 2 phần trái, phải.

Giới hạn: 1s, 256MB

Đầu vào:

Một xâu chữ số có độ dài từ 1 đế $10^{16}$ chữ số.
Tiếp theo là hai số tự nhiên a và b. $1 leq a,b leq 10^{8}$ .

Đầu ra:

In ra “YES” nếu có thể tách được xâu chữ số cho trước thỏa mãn yêu cầu. Và in lần lượt phần bên trái và phần bên phải sau khi tách.
In ra “NO” nếu không thể tách.

Sample I/O:

Input	Output
Testcase #1
116401024	YES
97 1024	11640
	1024

Testcase #2
284254589153928171911281811000	YES
1009 1000	2842545891539
	28171911281811000

Testcase #3
120	NO
12 1

2. Phân tích bài toán

Việc chia tách xâu chữ số thành 2 phần đồng nghĩa là ta chia phần bên trái k chữ số thì phần bên phải sẽ là n-k chữ số còn lại.

Gọi rema[i] là phần dư của phần bên trái từ chữ số đầu tiên (chỉ số 0) đến chữ số thứ i.

Gọi remb[i] là phần dư của phần bên phải từ chữ số thứ i đến hết.

Như vậy, ta cần tách sao cho rema[i] == 0 và remb[i+1] == 0. (Xem xét trường hợp phần bên phải bắt đầu bằng chữ số 0 thì không lấy.)

Xét ở phần bên trái: Khi ta thêm một chữ số nữa vào phần bên trái thì sẽ bằng phần bên trái trước đó nhân với 10 và cộng thêm giá trị chữ số đó. Như vậy, ta có: $rema[i] = (rema[i-1]*10 + C[i]) % a$ . Trong đó: C[i] là chữ số thứ i của xâu chữ số.
Xét ở phần bên phải: Khi ta thêm 1 chữ số nữa vào phần bên phải thì sẽ bằng phần bên phải trước đó cộng với giá trị chữ số đó nhân với lũy thừa của 10 cơ số L, với L là số lượng các chữ số của phần bên phải trước đó. Như vậy, ta có $remb[i] = (remb[i+1] + C[i]*P)%b$ . Trong đó: P là phần dư của $10^{L}$ cho b.

3. Code tham khảo

Vui lòng check ở dưới

Bài P151PROF spoj PTIT ROUND 1F – Cipher

0xb0b0 team là 1 đội của PTIT đang tham gia cuộc thi CTF (Capture The Flag). Để tìm được Flag của một câu hỏi, bạn phải trải qua rất nhiều thử thách. Đội đang tiến hành giải quyết 1 bài Cipher. Sau 1 hồi thi cử rất quyêt liệt, 0xb0b0 team đã đi đến kết luận: Secret key (khóa bí mật) có thể lấy được bằng cách cắt khóa Public key (công khai) thành 2 phần. Khóa công khai là 1 số tự nhiên rất lớn, có thể có tới 1 triệu chữ số.

0xb0b0 team muốn tìm một cách sao cho có thể cắt publickey thành 2 số nguyên dương x và y sao cho x chia hết cho a và y chia hết cho b (với a và b là 2 số cho trước). Cả x và y đều không được có chữ số 0 ở đầu.

Hãy giúp 0xb0b0 team tìm cách để cắt public key.

Input

Dòng thứ nhất chứa public key 1 số nguyên dương (Không chứa chữ số 0 ở đầu). có đồ dài từ 1 đến 10^6 chữ số.
Dòng tiếp theo bao gồm 2 số nguyên dương cách nhau bởi 1 dấu cách a, b(1 ≤ a, b ≤ 10^8).

Output

Dòng đầu tiên in “YES” nếu có cách cắt được public key. Trong trường hợp này, in 2 dòng tiếp theo là 2 số x, y sao cho x bé nhất có thể.

Trường hợp còn lại, tức là không tồn tại cách cắt, in “NO” và không in gì thêm.

Example

Test 1:

Input:

116401024

97 1024

Output:

YES

11640

1024

Test 2:

Input:

284254589153928171911281811000

1009 1000

Output:

YES

2842545891539

28171911281811000

Test 3:

Input:

120

12 1

Output:

Code tham khảo cho 2 bài bên trên. lưu ý về ý nghĩa 2 bài bên trên là giống nhau, nhưng về code của bài ở trên và bài ở dưới sẽ khác nhau. các bạn lưu ý để thôi lấy nhầm code CF nộp qa PTIT à :3

[sociallocker]

code bài trên CF

string C;
int a, b;
vi rema, remb;

int main(){
    cin >> C;
    cin >> a >> b;

    rema.resize(sz(C));
    remb.resize(sz(C));

    Rep(i, sz(C)){
        if(i == 0) rema[i] = (C[i] - '0')%a;
        else rema[i] = (rema[i-1]*10 + (C[i] - '0'))%a;
    }

    int P = 1;
    Repd(i, sz(C)){
        if(i == (sz(C)-1)){
            remb[i] = (C[i] - '0')%b;
        }else{
            P *= 10; P %= b;
            remb[i] = (remb[i+1] + (C[i] - '0')*P)%b;
        }
    }

    bool done = false;
    Rep(i, sz(C)-1){
        if(rema[i] == 0 && remb[i+1] == 0 && C[i+1] != '0'){
            cout << "YES" << endl;
            For(j, 0, i) cout << C[j];
            cout << endl;
            For(j, i+1, sz(C)-1) cout << C[j];
            cout << endl;
            done = true;
            break;
        }
    }
    if(!done)
        cout << "NO" << endl;
}

code bài trên PTIT

const   fi='';
        nmax=1000000;
type    data=longint;
var
        f:text;
        S:ansistring;
        a,b:data;
        lengA,LengB:data;
        RemA, RemB, pow:array[0..nmax+1] of data;

procedure docfile;
var     i,j:data;
        tmp:string;
begin
        assign(f,fi); reset(f);
        readln(f,s);
        read(f,a,b);
        close(f);
end;

procedure xuli;
var     i,j,tmp,p:data;
        s1,s2:string;
begin
        RemA[0]:=0;
        for i:=1 to length(s) do
                RemA[i]:=(RemA[i-1]*10+(ord(s[i])-48)) mod A;
        p:=1;
        RemB[length(s)+1]:=0;
        remb[length(s)]:=(ord(s[length(s)])-48) mod b;
        for i:=length(s)-1 downto 1 do
                begin
                        p:=p * 10; p:=p mod b;
                        RemB[i]:=(RemB[i+1]+(ord(s[i])-48)*p) mod b;
                end;
        for i:=1 to length(s)-1 do
                if (s[i+1]<>'0') and (remA[i]=0) and (RemB[i+1]=0) then
                        begin
                                writeln('YES');
                                writeln(copy(s,1,i));
                                writeln(copy(s,i+1,length(s)-i+1));
                                exit;
                        end;
        writeln('NO');
end;

begin
        docfile;
        xuli;
end.

1. Đề bài CF490C codeforces

2. Phân tích bài toán

3. Code tham khảo

Trả lời Hủy