Codeforces 547C Mike and Foam 容斥 - c++编程基础

TOP

Codeforces 547C Mike and Foam 容斥

2015-11-21 01:00:54 来源: 作者: 【大中小】浏览:1次

Tags：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; j
                
                 sqrt((double)i) || j == primenum - 1) { prime[primenum++] = i; break; } } int n, q; int a[N]; vector
                 
                  G[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); } set
                  
                   s; 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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Codeforces Round #305 (Div. 1) ..	下一篇：leetcode_Validate Binary Search..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: