fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef signed long long ll;
  5. const int MX = 1e6 + 5;
  6. int mu[MX];
  7. char prime[MX];
  8.  
  9. void sieve(){
  10. 	mu[1] = 1;
  11. 	for(int i = 2; i< MX; i++) mu[i] = -1, prime[i] = 1;
  12. 	for(int i = 2; i<MX; i++){
  13. 		if(prime[i]){
  14. 			mu[i] = 1;
  15. 			for(int j = 2 * i; j < MX; j += i){
  16. 				prime[j] = 0;
  17. 				mu[j] = (j % (i * i)) == 0 ? 0 : -mu[j];
  18. 			}
  19. 		}
  20. 	}
  21. }
  22.  
  23. int main() {
  24. 	sieve();
  25. 	int t;
  26. 	ll n, m;
  27. 	scanf("%d", &t);
  28.  
  29. 	for(int i = 1; i<=t; i++){
  30. 		scanf("%lld %lld", &n, &m);
  31. 		if(n > m) swap(n, m);
  32. 		ll Ans = n * m;
  33. 		for(int i = 2; i<=n; i++){
  34. 			Ans -= (ll)mu[i] * (ll)(n/i) * (ll)(m/i);
  35. 		}
  36. 		printf("%lld\n", Ans);
  37. 	}
  38. 	return 0;
  39. }
Success #stdin #stdout 0.01s 8352KB
comments (?)
stdin
copy 
3
1 2
4 2
3 5
stdout
copy 
2
6
12
https://ideone.com/mMoWMS
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!