>

LoeiJe

:D 获取中...

何以解忧？唯有暴富

欧拉函数

欧拉函数
poj-3126
素数筛

欧拉函数，即 $\varphi \left(x\right)$, 表示小于等于$n$和$n$互质的数的个数。
比如 $\varphi \left(1 \right) = 1$.
当 $n$ 是质数时，有 $\varphi \left(n \right) = n - 1$
利用唯一分解定理(算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。) 可以把一个整数唯一的分解为质数幂次的乘积。
设 $n = p_{i}^{k_{1}} \dots p_{s}^{k_{s}}$ 其中 $p_i$是质数,那么定义 $\varphi \left(n\right) = n * \prod_{i=1}^N \frac{p_i - 1}{p_i}$

性质

欧拉函数积性函数
如果 $gcd(a, b) = 1$, 那么 $\varphi \left(a * b\right) = \varphi \left(a\right) * \varphi \left(b\right)$
特别的 当 $n$ 是奇数时，$\varphi \left(2n\right) = \varphi \left(n\right)$

欧拉定理
oi-wiki欧拉定理

1
2
3
4
5
6
7
8
9
10
11
12
13
// 求欧拉函数值
int euler_phi(int n) {
    int m = int(sqrt(n + 0.5));
    int ans = n;
    for(int i = 2;i <= m;i++) {
        if(0 == n % i) {
            ans = ans / i * (i - 1);
            while(0 == n % i) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// 素数筛
// 欧拉筛在poj提交时会超时 因为多了个遍历判断next是否是素数，pri中存放的是素数
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

const int maxn = 10000;

int is_prime[maxn];
int vis[maxn] = {0};
int pri[maxn], phi[maxn];

string a, b;
bool v[maxn];
struct number {         //将数字绑定步数
    string num;
    int step;
    number(string s, int n) : num(s), step(n) {};
};
// 素数筛
/*
* 如果我们想要知道小于等于n有多少个素数呢？

* 一个自然的想法是我们对于小于等于n的每个数进行一次判定。这种暴力的做法显然不能达到最优复杂度，考虑如何优化。

* 考虑这样一件事情：如果x是合数，那么x的倍数也一定是合数。利用这个结论，我们可以避免很多次不必要的检测。

* 如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
*/

// 埃拉托斯特尼筛法
void sieve(int n) { // 埃式筛法
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	//int n = 9999;
	for (int i = 2; i <= n; ++i)
	if (is_prime[i])
	for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
	return;
}

void Eratosthenes_init(int n){
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2;i <= n; i++) {
        if(is_prime[i]) {
            for(int j = i * i;j <= n;j += i) {     // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i 的倍数开始，提高了运行速度
                is_prime[j] = 0;            // 是i的倍数的均不是素数
            }
        }
    }
}
// 欧拉筛法
// 欧拉函数
void init(int n) {
    int cnt = 0;
    for(int i = 2;i <= n;i++) {
        if(!vis[i]) {
            pri[cnt++] = i;
        }
        for(int j = 0; j < cnt; j++) {
            if(i * pri[j] >= n) break;
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;  // i 之前被 pri[j] 筛过了
        }
    }
}

//欧拉函数
void euler_init(int n) {
  phi[1] = 1;
  //pri[0] = pri[1] = 0;
  int cnt = 0;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      phi[i] = i - 1;
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] >= n) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j]) {
        phi[i * pri[j]] = phi[i] * (pri[j] - 1);        // prr[j] 是素数 phi[j] = pri[j] - 1
      } else {
        // i % pri[j] == 0
        // 换言之，i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
        // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
        // 掉就好了
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      }
    }
  }
}

// 求欧拉函数值
int euler_phi(int n) {
    int m = int(sqrt(n + 0.5));
    int ans = n;
    for(int i = 2;i <= m;i++) {
        if(0 == n % i) {
            ans = ans / i * (i - 1);
            while(0 == n % i) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

inline bool n_(int next){for(int i = 0;i < maxn;i++) if(next == pri[i]) return 1;return 0;}

int bfs() {
    int ans = 0;
    memset(v, false, sizeof(v));
    queue<number> que;
    //number n = number(a, 0);       //开始节点
    que.push(number(a, 0));
    while(!que.empty()) {
        number temp = que.front(); que.pop();
        //string c = temp.num;
        if(b == temp.num) {
            ans = temp.step;       //找到目标
            return ans;
        }
        for(int i = 3;i >= 0;i--) {
            int ibegin = i == 0 ? 1 : 0;    // 最高位1开始
            string c = temp.num;
            for(int j = ibegin;j < 10;j++) {
                c[i] = j + '0';
                int next = atoi(c.c_str());      //下一个数字
                //bool s = [next](){for(int i = 0;i < maxn;i++) if(next == pri[i]) return 1;return 0;};
                bool s = n_(next);
                if(!v[next] && s && temp.num != c) {
                 //if(!v[next] && is_prime[next] && temp.num != c) {
                    v[next] = true;
                    que.push(number(c, temp.step + 1));
                }
            }
        }
    }
    //cout << ans << endl;
    //return ans;
}

int main()
{
    int t;
    cin >> t;
    Eratosthenes_init(maxn);
    //sieve(maxn);
    //init(maxn);
    //euler_init(maxn);
    //cout << euler_phi(t) << endl;
    while(t--) {
        cin >> a >> b;
        int ans = bfs();
        cout << ans << endl;
    }
    return 0;
}
学习笔记