fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 1e6 + 10;
  33. int lsp[maxn], cnt[maxn];
  34. ll ans = 0LL;
  35. int a[maxn], p[10], nx, bp[256], dp[256], lb[256], tp[256];
  36. inline void upd(int x, int sgn){
  37. 	nx = 0;
  38. 	int a;
  39. 	while(x > 1){
  40. 		a = lsp[x];
  41. 		p[nx ++] = a;
  42. 		while(x % a == 0)
  43. 			x /= a;	
  44. 	}
  45. 	For(mask,0,tp[nx]){
  46. 		if(mask)
  47. 			dp[mask] = p[lb[mask]] * dp[mask ^ tp[lb[mask]]];
  48. 		else
  49. 			dp[mask] = 1;
  50. 		if(sgn < 0)
  51. 			cnt[dp[mask]] += sgn;
  52. 		if(bp[mask] % 2)
  53. 			ans += -1LL * sgn * cnt[dp[mask]];
  54. 		else
  55. 			ans += +1LL * sgn * cnt[dp[mask]];
  56. 		if(sgn > 0)
  57. 			cnt[dp[mask]] += sgn;
  58. 	}
  59. }
  60. bool in[maxn];
  61. int n, q;
  62. int main(){
  63. 	memset(lsp, -1, sizeof lsp);
  64. 	For(i,0,256){
  65. 		tp[i] = (1 << i);
  66. 		bp[i] = __builtin_popcount(i);
  67. 		lb[i] = __builtin_ctz(i);
  68. 	}
  69. 	For(i,2,maxn)
  70. 		if(lsp[i] == -1)
  71. 			for(int j = i;j < maxn;j += i)
  72. 				lsp[j] = i;
  73. 	scanf("%d %d", &n, &q);
  74. 	For(i,0,n)
  75. 		scanf("%d", a + i);
  76. 	while(q--){
  77. 		int i;
  78. 		scanf("%d", &i);
  79. 		-- i;
  80. 		if(!in[i])
  81. 			upd(a[i], +1);
  82. 		else
  83. 			upd(a[i], -1);
  84. 		in[i] = !in[i];
  85. 		printf("%lld\n", ans);
  86. 	}
  87.  
  88. }
  89.  
  90.  
  91.  
Success #stdin #stdout 0.03s 15840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IxkI9b
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!