fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define MUMAX 10000001
  5.  
  6. ll t, a, b;
  7. vector<ll> prime;
  8. int mu[MUMAX];
  9.  
  10. ll f(ll a, ll b){
  11.     ll m = min(a, b);
  12.     ll ans = 0;
  13.     for(int i=0; i < prime.size() && prime[i] <= m; i++){
  14.         ll ub = m/prime[i];
  15.         for(int j=1; j <= ub; j++){
  16.             ans += mu[j]*(a/prime[i]/j)*(b/prime[i]/j);
  17.         }
  18.     }
  19.     return ans;
  20. }
  21.  
  22. void calc_mu(){
  23.     bool is_composite[MUMAX];
  24. 	fill(is_composite, is_composite + MUMAX, false);
  25. 	is_composite[0] = is_composite[1] = true;
  26. 	mu[1] = 1;
  27. 	for(int i = 2; i < MUMAX; ++i){
  28. 		if (!is_composite[i]){
  29.             prime.push_back(i);
  30.             mu[i] = -1;
  31. 		}
  32. 		for(int j = 0; j < prime.size () && i * prime[j] < MUMAX; ++j){
  33. 			is_composite[i * prime[j]] = true;
  34. 			mu[i * prime[j]] = -mu[i];
  35. 			if (i % prime[j] == 0){
  36.                 mu[i * prime[j]] = 0;
  37.                 break;
  38. 			}
  39. 		}
  40. 	}
  41. }
  42.  
  43.  
  44. int main()
  45. {
  46.     calc_mu();
  47.     cin >> t;
  48.     while(t--){
  49.         cin >> a >> b;
  50.         cout << f(a, b) << endl;
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 2.02s 59680KB
comments (?)
stdin
copy 
10
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 100000
10000000 10000000
10000000 10000000
10000000 10000000
10000000 10000000
stdout
copy 
30
2791
275034
27497027
2749371266
27493560870
27493351185725
27493351185725
27493351185725
27493351185725
https://ideone.com/fuoYkk
language:
C++ (gcc 8.3)
created:
5 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!