CF594D REQ

2022-09-23 02:12:12 字數 1173 閱讀 5645

給出一個長度為 \(n\) 的數列,\(q\) 次詢問,每次詢問給出 \(l,r\),需要求出 \(\varphi(\prod ^_a[i])\bmod p\)。

\(n,q\leq 200000,a[i]\leq 10^6\)。

for (;j<=ask[i].r;j++)

for (int k=a[j];k>1;)

那麼整個問題就迎刃而解了。需要預處理逆元,否則時間複雜度多一個 \(\log n\)。

時間複雜度 \(o(n\log n\log a[i])\)。

#include #include #include using namespace std;

typedef long long ll;

const int n=200010,m=1e6+10,mod=1e9+7;

int n,q,m,a[n],last[m],v[m],prm[m],inv[m],ans[n];

struct query

ask[n];

bool cmp(query x,query y)

struct seg

void build(int x,int ql,int qr)

int mid=(ql+qr)>>1;

build(x*2,ql,mid); build(x*2+1,mid+1,qr);

pushup(x); }

void update(int x,int k,int val)

int mid=(l[x]+r[x])>>1;

if (k<=mid) update(x*2,k,val);

else update(x*2+1,k,val);

pushup(x); }

ll query(int x,int ql,int qr)

}seg;

int main()

sort(ask+1,ask+1+q,cmp);

for (int i=1,j=1;i<=q;i++)

ans[ask[i].id]=seg.query(1,ask[i].l,ask[i].r);

} for (int i=1;i<=q;i++)

printf("%d\n",ans[i]);

return 0;

}

CF594D REQ 樹狀陣列 質因數分解

給定序列 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 所以我們只需要處理出每一段區間內質因數...

CF 400 D

codeforces 400 d 題目大意 給出n扇門,m把鑰匙,和沒把鑰匙可以改變狀態 關 開,開 關》 的門的數量及對應編號 保證每個門...

CF 329 D

d題,lca是很明顯的。要注意的是,因為是除法,所以最多可以除x 2的有64次,當大於64時可以直接返回0。而且注意到可能會有很多值為1的邊,可以使用路徑壓縮,把邊為1的邊壓縮掉,類似於並查集的路徑壓縮。 之前只壓縮到lca,一直tle,可以直接壓縮到它們的根節點。 include include ...