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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.