好久沒發表解題心得到巴哈了
其實之前蠻多題目我也是 看完tutorial 搞很久才喇完
也是能寫出一點東西出來
主要是覺得解法太狗 沒什麼發文記錄下來的必要
但好像能寫心得的 就是這種狗解法 = =
有空我也會慢慢的翻之前覺得適合的題目po上來
以下就是我看完tutorial後
邊打邊解的詳解:
設 n = i(p-1)+j
當限制 i is N, 0 <= j < p-1 時 (在我的定義中自然數 N 包含 0)
每對相異的 i, j 恰能表示一個獨一無二的自然數 n
則有 na^n = (i(p-1)+j) * a^(i(p-1)+j) = (j-i) * a^j (mod p)
推導過程:
前項可因 乘法的分配律，可以被 %p 而得出
後者因 費馬小定理: a^(p-1) = 1
所以 a 的次方部分，可被 % (p-1)
我們枚舉所有的 j，此時 a^j 為定值
而符合的 j-i 值應為 b * a^-j (mod p)
其中 a^-j 為 a^j 的模 p 反元素
顯然 b * a^-j 在 % p 後也為定值
這邊可以利用費馬小定理求出模質數的反元素
我們設這個模反元素 y = a^-j
有 y * a^j = 1 (mod p)，又有 a^(p-1) = 1 (mod p)
因此可得 y = a^(p-1-j) (mod p)
回到 j-i 的部分，經過上述操作後我們得出
j-i = b * a^-j = by (mod p)
現在，我們得計算使 n 在 [1,x] 的 i 有多少個
由於上面那個式子被 % p 了
可以理解為每 p 個連續的自然數，就恰有一個符合的 i 值
因此我們可以先限縮 i 的範圍
將範圍大小 // p，即可得出大約有幾個符合的 i 了
現在我們就來用 n 推出 i 的範圍:
1 ≤ n = i(p-1)+j ≤ x
1-j ≤ i(p-1) ≤ x-j
(1-j)/(p-1) <= i <= (x-j)/(p-1)
思考一下就能得出:
左邊的除式可以用 ceil，右邊的可以用 floor
而左邊的除式被 ceil 顯然就是 0 了
因此範圍符合的 i 有:
(x-j)//(p-1) + 1 個
再將這個數 // p，就是符合的 i 大概的數量了
這邊說大概 是因為這個數要嘛是正確答案，要嘛是 正確答案-1
因為有可能即使 i 的範圍只有 1，卻剛好包含符合的 i
所以我們得先找出最小的 i
符合 j-i = by (mod p)
熟悉模算數的話就不難
j-i = by >>> -i = by-j >>> i = j - by (mod p)
基本上跟一般的等式操作沒兩樣
(j - by) % p 就是符合的最小 i 值了
而其他符合的 i 值就是加了任意個 p
但是當然也得符合範圍限制
這個最小的 i 可能會 > (x-j)/(p-1)
這樣就等於說這個 j 沒有任何符合的 i
這個在第一個範測就發生了，Wa 的話可能要注意這點
得到最小符合的 i 值之後
剩下就真的是每 p 個出一個符合的 i 了
