題目鏈接 https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1439

【題目描述】
有n個數(shù)字，a[1],a[2],…,a[n]。有一個集合，剛開始集合為空。然后有一種操作每次向集合中加入一個數(shù)字或者刪除一個數(shù)字。每次操作給出一個下標(biāo)x(1 ≤ x ≤ n)，如果a[x]已經(jīng)在集合中，那么就刪除a[x],否則就加入a[x]。

問每次操作之后集合中互質(zhì)的數(shù)字有多少對。

注意，集合中可以有重復(fù)的數(shù)字，兩個數(shù)字不同當(dāng)且僅當(dāng)他們的下標(biāo)不同。

比如a[1]=a[2]=1。那么經(jīng)過兩次操作1，2之后，集合之后存在兩個1，里面有一對互質(zhì)。

Input
單組測試數(shù)據(jù)。
第一行包含兩個整數(shù)n 和 q (1 ≤ n, q ≤ 2 × 10^5)。表示數(shù)字的種類和查詢數(shù)目。
第二行有n個以空格分開的整數(shù)a[1],a[2],…,a[n] (1 ≤ a[i] ≤ 5 × 10^5),分別表示n個數(shù)字。
接下來q行，每行一個整數(shù)x(1 ≤ x ≤ n)，表示每次操作的下標(biāo)。

Output
對于每一個查詢，輸出當(dāng)前集合中互質(zhì)的數(shù)字有多少對。
Input示例
樣例輸入1
5 6
1 2 3 4 6
1
2
3
4
5
1
樣例輸入2
2 3
1 1
1
2
1
Output示例
樣例輸出1
0
1
3
5
6
2
樣例輸出2
0
1
0
【思路】
如果已經(jīng)知道現(xiàn)在集合中有多少對互質(zhì)對，現(xiàn)在新加入一個元素x，那么只要計算這個xx和集合中的所有元素能夠形成多少個互質(zhì)對，加到答案中去，刪除元素同理. 問題就是要計算一個數(shù)字和一堆數(shù)字會組成多少互質(zhì)對，反過來考慮問題，也可以計算組成非互質(zhì)對的個數(shù)然后用集合的大小減去就得到互質(zhì)對的個數(shù)
那非互質(zhì)對怎么計算，假設(shè)新加入一個整數(shù)xx，原來集合中有一個元素uu，如果(x,u)(x,u)不是互質(zhì)對，那么gcd(x,u)!=1gcd(x,u)!=1 同時 gcd(x,u)gcd(x,u)的值一定是xx的一個因子，這里我們就可以遍歷xx的每一個大于1的因子，然后用容斥原理來計算了，具體怎么算這里舉個例子，比如現(xiàn)在集合SS中已經(jīng)有了5個元素，新加入一個x=24x=24，我們遍歷xx的所有大于1的因子2,3,4,6,8,12,242,3,4,6,8,12,24，如果集合SS中有約數(shù)為2的數(shù)，那么xx就會和SS中每一個有約數(shù)2的數(shù)產(chǎn)生一個非互質(zhì)對，同理其它的約數(shù)3,4,6,8...3,4,6,8...都是，但是會算重，如果已經(jīng)計算過SS中有約數(shù)為2的個數(shù)和約數(shù)為3的個數(shù)，那么其實已經(jīng)計算過了SS中有約數(shù)為6的個數(shù)了，而且還算了兩回，所以這里就要減掉了.而對于4,8,12,244,8,12,24而言，它們都已經(jīng)在計算2,32,3的時候算過了，可以發(fā)現(xiàn)這里新產(chǎn)生的互質(zhì)對的對數(shù)為5?S中有約數(shù)2的個數(shù)?S中有約數(shù)3的個數(shù)+S中有約數(shù)6的個數(shù)5?S中有約數(shù)2的個數(shù)?S中有約數(shù)3的個數(shù)+S中有約數(shù)6的個數(shù) 對于每個約數(shù)而言，前面的系數(shù)就是莫比烏斯函數(shù)的函數(shù)值
代碼中先把每個數(shù)的約數(shù)都預(yù)處理出來，然后在主函數(shù)中直接枚舉，要用輸入掛才能卡過去

#include<bits/stdc++.h> namespace fastIO {#define BUF_SIZE 100000//fread -> read1,bool IOerror = 0;inline char nc() {static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;if(p1 == pend) {p1 = buf;pend = buf + fread(buf, 1, BUF_SIZE, stdin);if(pend == p1) {IOerror = 1;return -1;}}return *p1++;}inline bool blank(char ch) {return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';}inline void read(int &x) {char ch;while(blank(ch = nc()));if(IOerror)return;for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');}#undef BUF_SIZE };using namespace std; using namespace fastIO; typedef long long ll;const int maxa=200005; const int maxn=500005;bool vis[maxn]; int prim[maxn]; int mu[maxn]; int cnt;void get_mu(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt && prim[j]*i<=n;j++){vis[prim[j]*i]=1;if(i%prim[j]==0) break;else mu[i*prim[j]]=-mu[i];}} }int n,q; int a[maxa]; bool in[maxa]; int c[maxn]; vector<int> g[maxn];void init(){get_mu(maxn-1);for(int i=1;i<maxn;++i){for(int j=i;j<maxn;j+=i){g[j].push_back(i);}} }int main(){init();read(n);read(q);for(int i=1;i<=n;++i) read(a[i]);ll ans=0;while(q--){int id,x;read(id);x=a[id];if(!in[id]){int num=g[x].size();for(int i=0;i<num;++i){int u=g[x][i];ans+=mu[u]*c[u];++c[u];}}else{int num=g[x].size();for(int i=0;i<num;++i){int u=g[x][i];--c[u];ans-=mu[u]*c[u];}}in[id]=!in[id];printf("%lld\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wafish/p/10465182.html

總結(jié)

以上是生活随笔為你收集整理的51Nod 1439 - 互质对（容斥+莫比乌斯函数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。