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.|

DHFUNC - Tính hàm

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/dhfunc


 

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 và 1, các phần tử sau đó
được thiết lập theo quy tắc mỗi phần tử bằng tổng hai phần tử trước nó. Công thức truy hồi của
dãy Fibonacci như sau:
Fibonacci(n) =
1
1
Fibonacci(n 1) Fibonacci(n 2)

    
Xét hàm f(x,y) sau:
f(x,y) =
( 1, ) ( , 1) ( , )
y
x
 f x y  f x y g x y

       
trong đó, g(x,y) là ước số chung lớn nhất của Fibonacci (x) và Fibonacci (y).
Yêu cầu: Cho 4 số nguyên không âm x, y, α, β và số nguyên dương B, hãy tính hàm f(x,y) mod B.
Dữ liệu: Vào từ thiết bị vào chuẩn: Dòng đầu tiên ghi số nguyên dương K là số lượng bộ dữ liệu.
Tiếp đến là K dòng, mỗi dòng chứa 5 số nguyên x, y, α, β, B tương ứng với một bộ dữ liệu. Các số
trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là giá trị hàm f tính
được tương ứng với bộ dữ liệu trong file dữ liệu vào.
Subtask 1 (20 điểm): Giả thiết là x, y ≤ 10; α, β, B ≤ 106.
Subtask 2 (20 điểm): Giả thiết là x, y ≤ 50; α, β, B ≤ 109.
Subtask 3 (15 điểm): Giả thiết là x, y ≤ 50; α, β, B ≤ 1018.
Subtask 4 (15 điểm): Giả thiết là x, y ≤ 500; α, β, B ≤ 1018.

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 và 1, các phần tử sau đó

được thiết lập theo quy tắc mỗi phần tử bằng tổng hai phần tử trước nó. Công thức truy hồi của

dãy Fibonacci như sau:

  • Fibonacci(n) = 1 với n = 1, 2
  • Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

Xét hàm f(x,y) sau:

  • f(x,y) = x nếu y = 0
  • f(x,y) = y nếu x = 0
  • f(x,y) = alpha * f(x-1,y) + beta * f(x,y-1) + g(x, y) nếu x, y > 0.

trong đó, g(x,y) là ước số chung lớn nhất của Fibonacci (x) và Fibonacci (y).

Yêu cầu: Cho 4 số nguyên không âm x, y, α, β và số nguyên dương B, hãy tính hàm f(x,y) mod B.

Dữ liệu: Vào từ thiết bị vào chuẩn: Dòng đầu tiên ghi số nguyên dương K là số lượng bộ dữ liệu.

Tiếp đến là K dòng, mỗi dòng chứa 5 số nguyên x, y, α, β, B tương ứng với một bộ dữ liệu. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là giá trị hàm f tính được tương ứng với bộ dữ liệu trong file dữ liệu vào.

  • Subtask 1 (20/70 điểm): Giả thiết là x, y ≤ 10; α, β, B ≤ 10^6.
  • Subtask 2 (20/70 điểm): Giả thiết là x, y ≤ 50; α, β, B ≤ 10^9.
  • Subtask 3 (15/70 điểm): Giả thiết là x, y ≤ 50; α, β, B ≤ 10^18.
  • Subtask 4 (15/70 điểm): Giả thiết là x, y ≤ 500; α, β, B ≤ 10^18.

Ví dụ:

Dữ liệu 

3

0 10 1 1 100

10 0 1 1 100

1 1 1 1 100

Kết quả

10

10

3

 


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-04-20
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSG Duyên hải và Đồng bằng Bắc Bộ 2014

hide comments
2019-03-28 14:10:21
Trâu AC
2019-03-28 14:10:13
Ez AC =))
2018-07-13 10:14:22
Dành cho ai muốn tham khảo :D
http://bit.ly/2D6yADp

Last edit: 2019-01-12 01:44:13
2017-09-17 10:52:26
cuối cùng cũng AC sau khoảng 9 tháng :v
@phanduy16
2017-03-27 15:39:24
x=0 y=0 thì ntn nhỉ :V
2015-06-14 14:15:31 Stupid Dog
@stupid_dog :

tại ăn cắp bản quyền nên mới WA đó
2014-10-17 12:04:49 stupid_dog
sao lại WA hoài vậy. @@
2014-04-24 04:33:00 NTT
PS xem giúp bài mình với, ko biết sai chỗ nào mà 0 điểm mãi...
2014-04-20 13:16:24 Anh Duc Le
Tối ưu code mãi vẫn chả biết TLE ở đâu, cuối cùng mới phát hiện ra là WA T_T
2014-04-20 12:16:36 BlackMouse
Bài này chỉ vướng bignum
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.