題意:給你一個n的全排列, q個操作, 每個操作是一個區間,要求求出這個區間中任意兩個數的gcd的最大值。
思路:一個數是兩個數的公約數, 等價於一個數可以被兩個整數同時整除。 所以我們可以算出每一個數的所有約數, 然後求一個區間中被超過兩個數整除的數中的最大值即可。
維護區間最大值, 我們可以用線段樹來維護。 因為我們難以同時維護一個區間, 所以我們離線處理, 按照r排序, 那麼每次如果當前數的一個約數曾經出現過, 就在之前出現的點加入線段樹, 每次順便查詢即可。
細節參見代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include