欧拉定理、欧拉函数、a/b%c

怕忘了……

欧拉函数定义、证明、打表方法

欧拉定理定义、证明

https://blog.csdn.net/zzkksunboy/article/details/73061013

剩余系、完系、简系

证明相当精彩！

$a_{i} * b + b_{j} * a$

而1~a*b中关于a*b的每个系有且仅有一个。

勿忘：积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

====================================================================

https://blog.csdn.net/u014074562/article/details/50990326

a^b%c

在b非常大时的情况，

[前提 (a,c)=1]

因为a^phi(c)%c = 1

a^b%c=a^(b%phi(c))%c

c为素数时，phi(c)=c-1。

[无前提]

b>=phi(c)时，a^b%c=a^(b%phi(c)+phi(c))%c

b<phi(c)时，a^b%c=a^(b%phi(c))%c (前面的定理不一定正确)

证明：

https://www.luogu.org/problemnew/solution/P5091

例子：

a=d c=d^e b=d^f e>f

如a=2 b=1024 c=2

P5091 【模板】欧拉定理

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=1e6+10;
15 //const int maxlen=2e7+10;
16 
17 int phi[maxn],zhi[maxn],cnt_zhi;
18 bool vis[maxn];
19 int maxv=1e6;
20 //char str[maxn];
21 
22 ll mul(ll a,ll b,ll m)
23 {
24     ll y=1;
25     while (b)
26     {
27         if (b&1)
28             y=y*a%m;
29         a=a*a%m;
30         b>>=1;
31     }
32     return y;
33 }
34 
35 int main()
36 {
37     ///互质：它们的公因数只有1
38     ///i=1~m的phi(i) 顺便求出
39 
40     bool use=0;
41     int i,j,k,a,b,m;
42     char c;
43     phi[1]=1;///
44     for (i=2;i<=maxv;i++)
45     {
46         if (!vis[i])
47         {
48             zhi[++cnt_zhi]=i;
49             phi[i]=i-1;
50         }
51         for (j=1;j<=cnt_zhi;j++)
52         {
53             k=i*zhi[j];
54             if (k>maxv)
55                 break;
56             vis[k]=1;
57             if (i%zhi[j]==0)
58             {
59                 phi[k]=phi[i]*zhi[j];
60                 break;
61             }
62             else
63                 phi[k]=phi[i]*(zhi[j]-1);
64         }
65     }
66 
67 
68     scanf("%d%d ",&a,&m);
69     b=0;
70     while ((c=getchar())!=EOF)
71     {
72         if (!(c>=48 && c<=57))
73             break;
74 
75         b=b*10+c-48;
76         if (b>=phi[m])
77             use=1;
78         b=b%phi[m];
79 //        b=(b*10+c-48)%phi[m];
80     }
81 
82     if (use)
83         printf("%lld",mul(a,b+phi[m],m));
84     else
85         printf("%lld",mul(a,b,m));
86     return 0;
87 }
88 /*
89 2 12 8
90 2 5 3
91 */

Advanced:

学习快速幂&龟速乘&快速乘

https://blog.csdn.net/Cyan_rose/article/details/83065026

------------------------------------

a/b%c

b,c互质

则a/b 与 a^[phi(c)-1] 模c的结果是一致的 [a^phi(c) mod c = 1]

a/b%c=a^[phi(c)-1]%c

对于任意情况：

针对的a是特别大，b、c较小的情况

a/b%c=(a%bc)/b

证明：把a设为bc*x + b*y +z的形式 (x尽量大，然后是y尽量大，x,y,z>=0)

=============================

最后推荐：

https://www.cnblogs.com/zwfymqz/p/6740325.html

一些数论题目的模板