fork download
copy 
  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. int EP(int m) {
  10. 	int res = m, cur = m;
  11. 	while (cur > 1) {
  12. 		int pf = sfac[cur];
  13. 		res -= res / pf;
  14. 		while (cur % pf == 0)
  15. 			cur /= pf;
  16. 	}
  17. 	return res;
  18. }
  19.  
  20. int main(int argc, char **argv) {
  21. 	for (int p = 0; p < N; ++p)
  22. 		sfac[p] = p;
  23. 	for (int p = 2; p * p < N; ++p)
  24. 		if (sfac[p] == p)
  25. 			for (int q = p * p; q < N; q += p)
  26. 				sfac[q] = min(sfac[q], p);
  27. 	int T;
  28. 	scanf("%d", &T);
  29. 	while (T-- != 0) {
  30. 		int m;
  31. 		scanf("%d", &m);
  32. 		int a = EP(m);
  33. 		int b = m - 1;
  34. 		printf("%lld\n", 1LL * a * b);
  35. 	}
  36. 	return 0;
  37. }
Success #stdin #stdout 0.01s 7012KB
comments (?)
stdin
copy 
2
6
10
stdout
copy 
10
36
https://ideone.com/yXLv7v
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!