Dãy Nguyên Tố Cùng Nhau - LQDOJ: Le Quy Don Online Judge

• 
• Trang chủ
• Giới thiệu Máy chấm Đề xuất ý tưởng Đề xuất bài tập Đề xuất kỳ thi Công cụ Báo cáo tiêu cực Báo cáo lỗi

Tiếng Việt

Tiếng Việt English

Đăng nhập

Đăng ký

Dãy nguyên tố cùng nhau

Xem PDF Nộp bài Tất cả bài nộp Các bài nộp tốt nhất Xem hướng dẫn Tác giả: admin Dạng bài number theory (số học), math (toán học), string (chuỗi), binary-search (chặt nhị phân) Điểm: 1800 (p) Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi hay tin TN đi chơi với Tuấn, trái tim ami tan vỡ. Chưa kịp vượt qua cú sốc này, lại nghe tin TN còn đi đêm với Blebleble, ami sụp đổ hoàn toàn. Âu đây cũng là do số trời, khi số cặp \((i,j)\) mà ami tìm được là \(0\) :((. Nhưng Ami là một con người mạnh mẽ, cậu quyết không để TN và những mối tình tay ba oan nghiệt làm mình đau đớn. Cậu quyết định sang crush LN, một cô gái học LQĐ. Nhưng trớ trêu thay, có vẻ số tình lận đận vẫn không buông tha ami khi LN đã là người trong mộng của ĐNLT. Tự nhủ anh em quan trọng hơn cả, cậu không tranh giành LN với ĐNLT nữa. Cậu chuyển sang một đối tượng mới hoàn toàn – LMH :)).

Lại nói LMH là cô bạn xinh xắn và vô cùng thông minh – đặc biệt trong môn tin học. Cô bé tự hứa không couple với những ai không code giỏi hơn mình. Vì thế bạn nữ đặt ra một tiêu chuẩn : những ai muốn LMH chấp nhận phải đưa ra một bài toán mà cô không thể giải được trong 1s !!!. ami lại là người thích thử thách, sau bao nhiêu phút miệt mài, cậu đã nghĩ ra một bài toán hay ho và quyết định đem nó làm lễ vật tán tỉnh LMH. LMH, sau khi nghĩ trong \(0.1s\) ban đầu, cô nhíu mày. \(0.5s\) tiếp theo, cô đưa tay vỗ trán. \(0.69s\) tiếp theo, cô lại dùng khăn thấm mồ hôi. \(1s\) trôi qua, ami mừng rỡ : “Thoát kiếp FA rồi :))”. Nhưng với bản tính thông minh của mình, LMH lại thách đố : "Nếu trong contest 8 lần này không bạn nào A/C được thì tớ sẽ chấp nhận cậu là người đầu tiên và duy nhất :v”. Vì vậy hôm nay, ami xin hân hạnh mang đến cho các bạn bài toán này, hi vọng không ai A/C để cậu có thể khoe với mẹ rằng mình đã có bạn gái xinh đẹp như thế.

Bài toán cực kì ngắn gọn và đơn giản. Các bạn được cho \(3\) số \(a,b,c\). Xét các số tự nhiên \(d\) từ \(1\) đến vô cùng, viết những số \(d\) thỏa mãn hai điều kiện :

• \(d>a\).
• Ước chung lớn nhất của \(d\) và \(b\) là \(1\).

thành một dãy số (tất nhiên dãy này cũng dài vô cùng). Các bạn hãy tìm số lớn thứ \(c\) của dãy số này.

Input

• Dòng đầu là một số nguyên dương \(q(q \leq 30000)\) là số bộ dữ liệu.
• \(q\) dòng tiếp theo, mỗi dòng sẽ chứa 3 số nguyên dương \(a,b,c\) là một bộ dữ liệu \((a,b,c \leq 1000000).\)

Output

• Các bạn cần in ra q số, mỗi số tương ứng là 1 câu trả lời cho bộ dữ liệu đó.

Example

Test 1

Input 3 3 4 5 4 5 6 5 6 7 Output 13 12 25 Note

• Với bộ số \(3\) \(4\) \(5\) ta sẽ có dãy số sau : \(5\) \(7\) \(9\) \(11\) \(13\) \(15\) … Số lớn thứ \(5\) là số \(13\).

• Với bộ số \(4\) \(5\) \(6\) ta sẽ có dãy số sau : \(6\) \(7\) \(8\) \(9\) \(11\) \(12\) \(13\) \(14\) \(\cdots\) Số lớn thứ \(6\) là số \(12\).

• Với bộ số \(5\) \(6\) \(7\) ta sẽ có dãy số sau : \(7\) \(11\) \(13\) \(17\) \(19\) \(23\) \(25\) \(29\) \(31\) \(\cdots\) Số lớn thứ \(7\) là số \(25\).

Bình luận (5)

Gần nhất Gần nhất Xa nhất Điểm Tải bình luận...