1. 欧拉函数
对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。例如φ(8)=4，因为1,3,5,7均和8互质。
对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1)
欧拉函数公式
$$
φ(x) = x \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times …..\times (1-\frac{1}{p_n})
$$
(其中p1, p2……pn为x的所有质因数，x是不为0的整数)*
φ(1) = 1（唯一和1互质的数(小于等于1)就是1本身）。
注意：每种质因数只一个。比如 12 = 2x2x3 ,则有
$$
euler(12) = 12 \times( 1-\frac{1}{2}) \times (1-\frac{1}{3}) = 4
$$
性质
当n为质数时，φ(n)=n−1
当n=p^k时（p是素数)，φ(n) = φ(p^k) = p^k-p^k -1=p^k-1(p-1)
若n,m互质，φ(nm) = φ(n)φ(m) = (n−1)(m−1)
若n是奇数，则φ(2n)=φ(n)
特殊性质
当a与n互质时(n>2)有 :
$$
a^{φ(n)}mod n = 1 (恒等于)
$$
此公式即 欧拉定理
当a与n互质,且n为质数时(即:gcd(a,n)=1)则上式有:
$$
a^{(n-1)} mod n = 1(恒等于)
$$
此公式即 费马小定理
3.小于n,且与n互质的数的和:
$$
\frac{φ(n)\times n}{2} (n>2)
$$
2.应用
$$
求7^{222}的个位数 \
求个位数,则是模10,故想到n=10,φ(10) = 4 \
由于7和10是互质, \
所以由欧拉定理得到:7^4 mod 10 = 1 \
故7^{222}mod10 = 7^{4*55} * 7^2 mod10 = 49mod10 = 9
$$
3.例题
给出L,求出最小、是L整数倍,并且每一位都是8的数字的长度。
每一位只有8，则想到
$$
1111…1111 \times 8 = (10^{n-1}+10^n+…+10^2+10^1+10^0) = \frac{10^n-1}{9} \times 8
$$
式子中n则是位数的长度
因为这个数字要被L整除，则想到同余式：
$$
L | 8 \times \frac{10^n-1}{9}
$$
$$
9L | 8 \times 10^n-1
$$
设d = gcd(8,L)
$$
\frac{9L}{d} | \frac{8}{d}\times 10^n - 1
$$
明显看出，9L/d 与 8/d是互质的
则得到
=>
$$
\frac{9L}{d} | 10^n-1
$$
此式子表示10^n-1是9L/d的整数倍
=>
$$
10^n -1 = m \times \frac{9L}{d}
$$
根据同余式子可以写成
=>
$$
10^n ≡ 1mod\frac{9L}{d}
$$
若10和9L/d不互质，则无解
如果互质，则有
$$
10^{φ(\frac{9L}{d})}≡1mod\frac{9L}{d}
$$ { }
但是题目要求是最小的指数，所以我们需要在ϕ(9L/d)的因子中看是否有快速幂取模后等于1的，并且我们只需要判断它的因子就足够了
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll L;
ll mul(ll a,ll b,ll mod){
ll ans = 0;
while(b){
if(b & 1)
ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans;
}
ll q_pow(ll a,ll b,ll mod){
ll ans = 1;
while(b){
if(b & 1)
ans = mul(ans,a,mod);
a = mul(a,a,mod);
b >>= 1;
}
return ans;
}
ll Euler(ll n){
ll ans = n;
for(ll 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;
}
ll gcd(ll a,ll b){
return b ? gcd(b,a%b) : a;
}
int main(){
int cas = 0;
while(~scanf("%lld",&L)){
if(L == 0) break;
ll p = 9 * L / gcd(L,8);
ll d = gcd(10,p);
if(d != 1){
printf("Case %d: 0\n",++cas);
}
else{
ll phi = Euler(p);
ll ans = phi;
ll m = sqrt((double)phi);
bool flag = false;
for(int i = 1; i <= m; i++){
if(phi % i == 0 && q_pow(10,i,p) == 1){
ans = i;
flag = true;
break;
}
}
if(!flag){
for(int i = m; i >= 2; i--){
if(phi % i == 0 && q_pow(10,phi/i,p) == 1){
ans = phi / i;
break;
}
}
}
printf("Case %d: %lld\n",++cas,ans);
}
}
return 0;
}
|
https://blog.csdn.net/codeswarrior/article/details/81474958
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
typedef long long LL;
char b[1000006] ;
LL a ,c ;
LL qpower(LL a ,LL b ,LL mod ) {
LL ans = 1 ;
while(b){
if(b&1) {
ans = ans* a%mod ;
}
a = a*a %mod ;
b>>=1 ;
}
return ans %mod;
}
LL phi(LL n) {
LL ans = n ;
for(int i = 2 ; i*i<=n ; i++ ) {
if(!(n%i)){
ans = ans/i*(i-1) ;
while(n%i == 0 ){
n/=i ;
}
}
}
if(n>1) ans = ans/n*(n-1) ;
return ans ;
}
int main(){
while(~scanf("%lld %s %lld",&a,b,&c)){
LL len = strlen(b) ;
LL p = phi(c) ;
LL ans = 0 ;
for(LL i = 0 ; i<len ; i++){
ans = (ans*10 +b[i] -'0')%p ;
}
ans +=p ;
printf("%lld\n",qpower(a,ans,c));
}
return 0 ;
}
|
