HDU-2588-GCD

• 欧拉函数

  Accepted

  2588

  15MS

  1372K

  916 B

  G++

  #include "bits/stdc++.h"
  using namespace std;
  int euler(int n) {
      int ans = n;
      for (int i = 2; i * i <= n; i++) {
          if (n % i == 0) {
              ans = ans / i * (i - 1);
              while (n % i == 0) {
                  n /= i;
              }
          }    
      }
      if (n != 1) {
          ans = ans / n * (n - 1);
      }
      return ans;
  }
  int main() {
      int t, n, m, i;
      scanf("%d", &t);
      while (t--) {
          int ans = 0;
          scanf("%d%d", &n, &m);
          for (i = 1; i * i < n; i++) {
              if (n % i == 0) {
                  if (i >= m) {
                      ans += euler(n / i);
                  }
                  if (n / i >= m) {
                      ans += euler(i);
                  }
              }
          }
          if (i * i == n && n / i >= m) {
              ans += euler(n / i);
          }
          printf("%d
  ", ans);
      }
      return 0;
  }

  欧拉函数（euler）用于快速求出小于n并且和n互质的正整数的个数