fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using ll = long long;
  7. const int N = 1e7 + 5;
  8. int n, m;
  9. ll euler[N];
  10. ll ans = 0;
  11. bool prime[N];
  12. int p[N];
  13.  
  14. namespace sub1 {
  15. void solve() {
  16.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (__gcd(i, j) == 1) ans++;
  17.     cout << ans;
  18. }
  19. };
  20. namespace sub2 {
  21. void sieve_euler_phi(){
  22.     for (int i = 0; i <= n; i++) euler[i] = i;
  23.  
  24.     prime[0] = prime[1] = 1;
  25.     for (int i = 2; i * i <= n; i++){
  26.         if (!prime[i]){
  27.             for (int j =  i * i; j <= n; j += i){
  28.                 prime[j] = true;
  29.             }
  30.         }
  31.     }
  32.  
  33.     for (int i = 1; i <= n; i++){
  34.         if (!prime[i]){
  35.             for (int j = i; j <= n; j += i){
  36.                 euler[j] -= euler[j] / i;
  37.             }
  38.         }
  39.     }
  40.     euler[1] = 1;
  41. }
  42. void solve() {
  43.     sieve_euler_phi();
  44.     for (int i = 1; i <= n; i++) ans += euler[i];
  45.     ans = ans * 2 - 1;
  46.     cout << ans;
  47. }
  48. };
  49. namespace subfull {
  50. void sieve_prime() {
  51.     prime[0] = prime[1] = 1;
  52.     for (int i = 1; i <= n; i++) p[i] = i;
  53.     for (int i = 2; i * i <= n; i++){
  54.         if (!prime[i]) {
  55.             for (int j = i * i; j <= n; j += i) {
  56.                 prime[j] = true;
  57.                 p[j] = min(i, p[j]);
  58.             }
  59.         }
  60.     }
  61. }
  62. inline int calc(int x) {
  63.     int cnt = 0, pre = -1;
  64.     while (x != 1) {
  65.         int t = p[x];
  66.         if (t == pre) return -1;
  67.         x /= t;
  68.         cnt++;
  69.         pre = t;
  70.     }
  71.     return cnt;
  72. }
  73. void sieve(){
  74.     for (int i = 1; i <= n; i++) euler[i] = m;
  75.     for (int i = 2; i <= n; i++) {
  76.         int x = calc(i);
  77.         if (x != -1) {
  78.             int val = m / i;
  79.             if (x & 1) val *= -1;
  80.             for (int j = i; j <= n; j += i) euler[i] += val; 
  81.         }
  82.     }
  83. }
  84. void solve() {
  85.     sieve_prime();
  86.     sieve();
  87.     for (int i = 1; i <= n; i++) ans += euler[i];
  88.     cout << ans;
  89. }
  90. };
  91.  
  92. signed main() {
  93.     cin.tie(NULL)->sync_with_stdio(false);
  94.     if(ifstream("CGCD.inp")) {
  95.         freopen("CGCD.inp", "r", stdin);
  96.         freopen("CGCD.out", "w", stdout);
  97.     }
  98.     cin >> n >> m;
  99.     if (n <= 1000 && m <= 1000) return sub1::solve(), 0;
  100.     if (n <= 1e6 && n == m) return sub2::solve(), 0;
  101.     if (n > m) swap(n, m);
  102.     return subfull::solve(), 0;
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ysB5Gt
language:
C++14 (gcc 8.3)
created:
1 day 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!