fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const int N = 1000000 + 10;
  5. int phi[N];
  6.  
  7. int main() {
  8. 	for(int i=0; i<N; ++i)
  9. 		phi[i] = i;
  10. 	for(int i=2; i<N; ++i)
  11. 		if(phi[i] == i)
  12. 			for(int j=i; j<N; j+=i)
  13. 				phi[j] -= phi[j] / i;
  14. 	int m;
  15. 	int t;
  16. 	scanf("%d", &t);
  17. 	while(t--) {
  18. 		scanf("%d", &m);
  19. 		printf("%lld\n", (ll)phi[m]*(m-1));
  20. 	}
  21. 	return 0;
  22. }
Success #stdin #stdout 0.03s 7136KB
comments (?)
stdin
copy 
2
6
10
stdout
copy 
10
36
https://ideone.com/Vz5u8p
language:
C++14 (gcc 8.3)
created:
6 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!