fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int N = 1e6 + 1;
  7. int sfac[N];
  8.  
  9. void PF(int m, vector<int> &pf) {
  10. 	int cur = m;
  11. 	while (cur > 1) {
  12. 		int p = sfac[cur];
  13. 		pf.push_back(p);
  14. 		while (cur % p == 0)
  15. 			cur /= p;
  16. 	}
  17. }
  18.  
  19. int coprimes(int m) {
  20. 	int res = m;
  21. 	vector<int> pf;
  22. 	PF(m, pf);
  23. 	int n = pf.size();
  24. 	for (int mask = 1; mask < (1 << n); ++mask) {
  25. 		int mul = 1, ones = 0;
  26. 		for (int i = 0; i < n; ++i)
  27. 			if (((mask >> i) & 1) == 1) {
  28. 				++ones;
  29. 				mul *= pf[i];
  30. 			}
  31. 		if ((ones & 1) == 0)
  32. 			res += m / mul;
  33. 		else
  34. 			res -= m / mul;
  35. 	}
  36. 	return res;
  37. }
  38.  
  39. int main(int argc, char **argv) {
  40. 	for (int p = 0; p < N; ++p)
  41. 		sfac[p] = p;
  42. 	for (int p = 2; p * p < N; ++p)
  43. 		if (sfac[p] == p)
  44. 			for (int q = p * p; q < N; q += p)
  45. 				sfac[q] = min(sfac[q], p);
  46. 	int T;
  47. 	scanf("%d", &T);
  48. 	while (T-- != 0) {
  49. 		int m;
  50. 		scanf("%d", &m);
  51. 		int a = coprimes(m);
  52. 		int b = m - 1;
  53. 		printf("%lld\n", 1LL * a * b);
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0.01s 7096KB
comments (?)
stdin 
2
6
10
stdout 
10
36
https://ideone.com/s4EdLm
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!