https://oj.luyencode.net/problem/PTIT046

[utterances-bot]

Chi tiết bài tập - Luyện Code Online

https://oj.luyencode.net/problem/PTIT046

[mcscoder]

Bài này theo cách của mình:

• Ý tưởng: Phân tích thừa số nguyên tố, kiểm tra số lượng số nguyên tố 2 bên, sau đó tiến hành chia, mỗi lần chia là một bước Bước 1: Phân tích thừa số nguyên tố Bước 2: Kiểm tra tính khả thi:
• Nếu số lượng số nguyên tố lớn hơn 5 (>5) trong mỗi số bằng nhau ==> có thể
• Nếu cả 2 số đều không có số nguyên tố nào lớn hơn 5 (>5) ==> có thể
• Nếu số lượng số nguyên tố lớn hơn 5 (>5) trong mỗi số không bằng nhau ==> không thể ==> -1 Bước 3: Tiến hành chia:
• Để mà 2 số bằng nhau thì số lượng thừa số nguyên tố trong nó cũng phải bằng nhau
• Lấy số lượng số nguyên tố trong 2 số trừ cho nhau sau đó trị tuyệt đối để lấy số dương Ví dụ: 20 có thừa số nguyên tố = [2, 2, 5] 30 = [2, 3, 5] Cho biến count = 0
• Số lượng số 2 bên 20 là 2 còn bên 30 là 1, vậy ta phải cân bằng số lượng lấy count += abs(2-1) ==> count = 1
• Cứ như vậy, số 3 bên 20 là 0 còn bên 30 là 1, vậy count += abs(0 - 1) ==> count = 2
• Số 5 bên 20 là 1 bên 30 cũng là 1, vậy count += abs(1 - 1) ==> count = 2

Vậy ta có số bước là 2 Mình để code minh họa ở đây: https://ideone.com/0k8Imm Bạn nào chưa làm được tham khảo

[danh2006]

Đây là lời giải của mình đã AC. Nếu bạn đã cố gắng mà chưa làm được thì có thể tham khảo lời giải của mình.

Xem code AC

#include using namespace std; #define ll long long #define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);srand(time(NULL)); template void read(H& head) { cin >> head; } template void read(H& head, T& ...tail) { cin >> head; read(tail...); } template void write(H head) { cout << head << '\n'; } template void write(H head, T ...tail) { cout << head << " "; write(tail...); } template void print(T ...tok) { write(tok...); return; } int gcd(ll a, ll b){ if(b == 0) return a; else return gcd(b, a % b); } void solve(){ ll a, b, cnt = 0; read(a, b); ll x = gcd(a, b); while(a != x){ if(a % 5 == 0 && (a - (a * 4 / 5)) % x == 0) a = a - (a * 4 / 5); else if(a % 3 == 0 && (a - (a * 2 / 3)) % x == 0) a = a - (a * 2 / 3); else if(a % 2 == 0 && (a / 2) % x == 0) a /= 2; else{ write("-1"); return; } cnt++; } while(b != x){ if(b % 5 == 0 && (b - (b * 4 / 5)) % x == 0) b = b - (b * 4 / 5); else if(b % 3 == 0 && (b - (b * 2 / 3)) % x == 0) b = b - (b * 2 / 3); else if(b % 2 == 0 && (b / 2) % x == 0) b /= 2; else{ write("-1"); return; } cnt++; } write(cnt); } int main(){ fast_io; solve(); return 0; }

[sseu18042004]

test 2 là trường hợp đi với số 1 nha mọi người (1 3) ra 1.........(1,5) ra 1. 1 7 ra -1