程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 547C Mike and Foam 容斥

Codeforces 547C Mike and Foam 容斥

編輯：C++入門知識

Codeforces 547C Mike and Foam 容斥

題意：

給定n個數，q個操作

下面n個數 a1-an

開始有一個空的集合

每個操作一個數字 u (1<=u<=n) 表示把 a[u] 插入集合（若集合中沒有a[u]), 否則就把a[u]從集合中刪除

每個操作結束後輸出當前集合內有多少對數是互質的。

思路：

分解質因素，然後容斥一下求與a[u] 不互質的個數，做個差即可。

PS: 在微軟（蘇州）bop現場和kuangbin，19891101 ，Jayye, xiaoxin等晚上一起在賓館打的cf~

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}

typedef long long ll;
const int N = 5e5 + 10;

int prime[N], primenum;//有primenum個素數 math.h  
void PRIME(ll Max_Prime){
	primenum = 0;
	prime[primenum++] = 2;
	for (ll i = 3; i <= Max_Prime; i += 2)
	for (ll j = 0; jsqrt((double)i) || j == primenum - 1)
	{
		prime[primenum++] = i;
		break;
	}
}
int n, q;
int a[N];
vectorG[N];
ll ans;
void pre(int u, int x){
	for (int i = 0; prime[i] * prime[i] <= x; i++){
		if (x%prime[i] == 0){
			while (x%prime[i] == 0)x /= prime[i];
			G[u].push_back(prime[i]);
		}
	}
	if (x != 1)
		G[u].push_back(x);
}
sets;
int f[N];
int c[N], top;
void dfs(int t, int x, int cnt, int flag, int val){
	if (t >= (int) G[x].size())
	{
		if (cnt == 0)return;
		ans += f[val] * flag;
		c[top++] = val;
		return;
	}
	dfs(t + 1, x, cnt, flag, val);
	dfs(t + 1, x, cnt + 1, flag*-1, val*G[x][t]);
}
void p(){
	printf( set:); 
	for (auto it : s){
		printf(%d , it);
	}
	puts();
}
int one;
int main(){
	PRIME(N);
	rd(n); rd(q);
	for (int i = 1; i <= n; i++) {
		rd(a[i]);
		pre(i, a[i]);
	}
	ans = 0;
	one = 0;
	while (q--){
		int u; rd(u);
		if (a[u] == 1)
		{
			if (s.count(u))
			{
				one--;
				s.erase(u);
				ans -= s.size();
			}
			else {
				ans += s.size();
				one++;
				s.insert(u);
			}
		}
		else
		{
	//		printf(ans:%d, one:%d ); p();
			if (s.count(u))
			{
				s.erase(u);
				ans -= s.size();
				top = 0;
				dfs(0, u, 0, -1, 1);
				ans--; //刪掉自己與自己的組合
				for (int i = 0; i < top; i++)f[c[i]] --;
			}
			else {
				ans += s.size();
				s.insert(u);
				top = 0;
				dfs(0, u, 0, 1, 1);
				for (int i = 0; i < top; i++)f[c[i]] ++;
			}
		}
		cout <<    ; pt(ans); puts();
	}
	return 0;
}