#41359: 不需要從0檢查到L


jimmy19980625@gmail.com (張軒愷)

School : No School
ID : 261552
IP address : [123.194.35.10]
Last Login :
2024-02-03 06:45:39
j031. 11934 - Magic Formula -- UVA | From: [123.194.35.10] | Post Date : 2024-07-20 01:53

以題目的其中一筆測資為例

1 2 3 3 5 表示 a = 1, b = 2, c = 3, d = 3, L = 5;

檢查範圍 0 <= x <= 5, f(x) % 3 = 0, 符合的 x 有 0, 1, 3, 4

若L的數字不小,檢查會很費時

其實其中存在著規律,把要檢查的範圍分割成每個區域有d個數字

會變成

[0 ~ d - 1], [d ~ 2d - 1], [2d ~ 3d - 1], ......, [nd ~ L] (n為某個正整數)

先檢查第一個區域有哪些數字符合

如果0符合,那麼 d, 2d, 3d, ......, nd都會符合

如果1符合,那麼 d + 1, 2d + 1, 3d + 1, ......, nd + 1都會符合

以此類推...

------------------------------------------------------------------------------

計算的部分

第一個區域的數字為 mod d 的所有可能結果

如果0符合,計算 0~L有多少個數字 mod d 為 0

如果1符合,計算 0~L有多少個數字 mod d 為 1

 
ZeroJudge Forum