挑战程序竞赛系列（39）：4.1模运算的世界（2）

用户1147447

发布于 2019-05-26 09:40:08

2720

发布于 2019-05-26 09:40:08

文章被收录于专栏：机器学习入门

挑战程序竞赛系列（39）：4.1模运算的世界（2）

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 1284: Primitive Roots

POJ 1284: Primitive Roots

欧拉函数这东西我只知道一个定义：

欧拉函数的值等于不超过m并且和m互素的个数。

表达式如下：

ϕ(m)=m×∏ipi−1pi

\phi(m) = m \times \prod_{i} {\frac{p_i - 1}{p_i}}

其中m=pe11pe22⋯perrm = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}，当然我们可以简单证明下，只说一些思路。

首先，如果m是素数，可以直接得到ϕ(m)=m−1\phi(m) = m - 1，进一步得，mkm^k的欧拉值为ϕ(mk)=mk−mk−1\phi(m^k) = m^k - m^{k - 1}，令p = m，p为素数，于是得：

ϕ(p)=p−1ϕ(pk)=pk−pk−1

\phi(p) = p - 1 \ \phi(p^k) = p^k - p^{k-1}

有了这两条定理，我们只需要证明欧拉函数满足乘性函数即可，具体可以参考《初等数论及其应用》P175页。

此题，则用到了《初等》P249，定理9.5

定理：如果p有原根，则它恰有φ(φ(p))个不同的原根（无论p是否为素数都适用） p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根

欧拉函数的实现参考《挑战》P292，经历了三个版本。

代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P1284.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    void solve() {
        while (more()){
            int P = ni();
            out.println(euler_phi1(P - 1));
        }
    }

//  public int euler_phi(int n){  // n * (pi - 1) / pi = n / pi * (pi - 1)
//      int res = n;
//      while (n > 1){
//          for (int i = 2; i <= n; ++i){
//              if (n % i == 0){
//                  res = res / i * (i - 1);
//                  while (n % i == 0){
//                      n /= i;
//                  }
//              }
//          }
//      }
//      return res;
//  }

    public int euler_phi1(int n){  // n * (pi - 1) / pi = n / pi * (pi - 1)
        int res = n;
        for (int i = 2; i <= n / i; ++i){
            if (n % i == 0){
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }

        if (n != 1) res = res / n * (n - 1);
        return res;
    }

    int MAX_N = 65536 + 16;
    int[] euler;
    public void euler_phi2(){  //如果是素数 欧拉函数为 p - 1
        euler = new int[MAX_N];
        for (int i = 0; i < MAX_N; ++i) euler[i] = i;
        for (int i = 2; i < MAX_N; ++i){
            if (euler[i] == i){
                for (int j = i; j < MAX_N; j += i){
                    euler[j] = euler[j] / i * (i - 1);  // 
                }
            }
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

打表快点，但对内存要求高。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年08月29日，如有侵权请联系 cloudcommunity@tencent.com 删除

github