CF594D REQ 樹狀陣列 質因數分解

2022-09-22 21:55:02 字數 1183 閱讀 9345

給定序列 \(a_1,a_2,\dots a_n\) ,\(q\) 次詢問 \(l,r\),求 $ \phi(\prod_^r a_i)$

範圍&性質 : \(1\le n,q\le 2\times 10^5,1\le a_i\le 10^6\)

前置芝士:\(\phi(n)=n\times \prod(1-\frac)\)

所以我們只需要處理出每一段區間內質因數的並集,然後乘上它的影響,還要維護一個字首積

那麼問題就轉化成了,如何處理出一段區間內質因數的並集,我們發現這個東西等價於求區間內質因數的種類,和 採花 / hh的項鍊 這兩道題很類似,不過每個物品的價值變成了 \(\frac\), 對詢問離線,直接用樹狀陣列維護區間內每種質因數最後出現的位置,然後每次遇見一個新的數將區間內它的質因數最後的位置一更新

複雜度\(o(n\log n)\)

#includeusing namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 2e5+5;

const int maxm = 1e6+5;

const long long mod = 1e9+7;

long long n,qt,cnt;

long long a[maxn],c[maxm],f[maxn],ans[maxn],p[maxn],lst[maxm];

bool vis[maxm];

struct que

return res; }

void init()

for(int j=1;j<=cnt&&i*p[j]<=1000000;j++)

} }

inline long long lowbit(int x)

long long query(long long x)

void update(long long x,long long val)

void insert(long long x)

if(tmp>1)

return ; }

void work()

for(int i=1;i<=qt;i++) printf("%lld\n",ans[i]); }}

int main()