欧拉筛法 & 欧拉函数



前言

期末考考完前再码文我就剁手 (｡•ˇ‸ˇ•｡)

  1. 欧拉函数与欧拉筛法
    http://debug18.com/posts/introduction-to-sieve-method/

Bi-shoe and Phi-shoe - LightOJ - 1370

题意
给定n个数，对于每一个数，求xi，使得Φ(xi) >= ai，同时使得sum(xi)最小
思路
使用打表思想求出phi，再用hash思想输出phi_to_number（记为mp），只需打到1e6即可，最后因为题目求的是>=，因此滚动更新mp[i] = min(mp[i], mp[i + 1])，对于输入累加mp[i]即可

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long ll;
  const int N   = 1e6 + 15;
  const int inf = 0x3f3f3f3f;

  int prime[N], phi[N], mp[N];
  int prime_tot;
  bool used[N];

  void euler(){
      memset(used, true, sizeof(used));
      memset(mp, 0x3f, sizeof(mp));
      prime_tot = 0;
      phi[1] = 1;

      for(int i = 2; i < N; i++){
          if(used[i]){
              prime[prime_tot++] = i;
              phi[i] = i - 1;
              mp[phi[i]] = min(mp[phi[i]], i);
          }
          for(int j = 0; i*prime[j] < N; j++){
              used[i*prime[j]] = false;
              if(i%prime[j] == 0){
                  phi[i*prime[j]] = phi[i] * prime[j];
                  mp[phi[i*prime[j]]] = min(mp[phi[i*prime[j]]], i*prime[j]);
                  break;
              }else{
                  phi[i*prime[j]] = phi[i] * (prime[j] - 1);
                  mp[phi[i*prime[j]]] = min(mp[phi[i*prime[j]]], i*prime[j]);
              }
          }
      }
      for(int i = N - 2; i >= 0; i--){ mp[i] = min(mp[i], mp[i + 1]);  }
  }

  int main(){
      euler();
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          int n, tmp;
          ll  sum = 0;
          scanf("%d", &n);
          while(n--){
              scanf("%d", &tmp);
              sum += (ll)mp[tmp];
          }
          printf("Case %d: %lld Xukha\n", csn++, sum);
      }
  }


Farey Sequence - POJ - 2478

题意
（不会翻译）
思路
容易看出 f(n) = f(n-1) + phi(n)

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long ll;
  const int N   = 1e6 + 15;
  const int inf = 0x3f3f3f3f;

  int prime[N], phi[N];
  int prime_tot;
  bool used[N];
  ll  f[N];

  void euler(){
      memset(used, true, sizeof(used));
      prime_tot = 0;
      phi[1] = 1;

      for(int i = 2; i < N; i++){
          if(used[i]){
              prime[prime_tot++] = i;
              phi[i] = i - 1;
          }
          for(int j = 0; i*prime[j] < N; j++){
              used[i*prime[j]] = false;
              if(i%prime[j] == 0){
                  phi[i*prime[j]] = phi[i] * prime[j];
                  break;
              }else{
                  phi[i*prime[j]] = phi[i] * (prime[j] - 1);
              }
          }
      }
  }

  int main(){
      euler();
      f[2] = 1;
      for(int i = 3; i < N; i++){
          f[i] = f[i - 1] + (ll)phi[i];
      }

      int n;
      while(scanf("%d", &n) && n){
          printf("%lld\n", f[n]);
      }
  }


GCD - Extreme (II) - UVA - 11426

思路
可用Mobius求解，个人还不会 QAQ，故用欧拉函数推导求解，过程比较长，直接上图

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long ll;
  const int N   = 4e6 + 15;
  const int inf = 0x3f3f3f3f;

  int prime[N], phi[N];
  int prime_tot;
  bool used[N];
  ll  f[N];
  ll  sum[N];

  void init(){
      memset(used, true, sizeof(used));
      memset(sum, 0, sizeof(sum));
      prime_tot = 0;
      phi[1] = 1, phi[1] = 0;

      for(int i = 2; i < N; i++){
          if(used[i]){
              prime[prime_tot++] = i;
              phi[i] = i - 1;
          }
          for(int j = 0; i*prime[j] < N; j++){
              used[i*prime[j]] = false;
              if(i%prime[j] == 0){
                  phi[i*prime[j]] = phi[i] * prime[j];
                  break;
              }else{
                  phi[i*prime[j]] = phi[i] * (prime[j] - 1);
              }
          }
      }

      for(int i = 1; i < N; i++){
          for(int j = 1; i*j < N; j++){
              sum[i*j] += phi[j] * i;
          }
      }

      f[2] = 1, sum[2] = 1;
      for(int i = 3; i < N; i++){
          f[i] = f[i - 1] + sum[i];
      }
  }

  int main(){
      init();
      int n;
      while(scanf("%d", &n) && n){
          printf("%lld\n", f[n]);
      }
  }