快快幂的法子半数以上要快(尤其对于,则称a关于模p的乘法逆元为x

逆元定义

若\(a*x\equiv1 (\bmod
{b})\),且\(a\)与 class=”math inline”>\(b\)互质,那么大家就能定义:
\(x\)为 class=”math inline”>\(a\)的逆元,记为 class=”math inline”>\(a^{-1}\),所以我们也足以称 class=”math inline”>\(x\)为 class=”math inline”>\(a\)的倒数,
上列总结都在$\bmod b $意义下。

故此对于\(\frac{a}{b} (\bmod
{p})\),大家就能够求出 class=”math inline”>\(b\)在 class=”math inline”>\(\bmod {p}\)
下的逆元,然后乘上\(a\),再 class=”math inline”>\(\bmod {p}\),就是以此乘法逆元的值了。

那么,$inv[i]$能够等于$-(M/i)*inv[M\%i]$。

乘法逆元(欧拉函数,欧拉定理,质数筛法),欧拉

如果$ax{\equiv}1(mod\,p)$,且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。

有2个标题,在求解进度中有除法,答案非常大,需要最终答案对某数p取模。鲜明,由于除法的出现,每1回运算之后取模是对事情没有什么益处的。(比如:求1*7/2,答案对5取模。借使每2回运算取模也正是7%5/2%5,会拿走1,正确结果却是3)如若不想高精度把最终结果算出来再取模的话,有三个格局,正是把除以x转换为乘上x关于模p的乘法逆元。(事实上,乘法逆元应该视为线性同余方程的解也正是有个别数而不是二个数,可是一般只供给运用任意二个(比如最小正整数解)就能不辱任务职务)

何以能那样做:

设c是b关于模m的逆元,即$b∗c{\equiv}1(mod\,m)$,那么有$a/b{\equiv}(a/b)∗1{\equiv}(a/b)∗b∗c{\equiv}a∗c(mod\,m)$

求法:

1.恢宏欧几里得

$ax{\equiv}1(mod\,p)$,那么能够设$ax-1=p(-y)$,那么$ax+py=1=gcd(a,p)$,求解即可

2.欧拉定理(费马小定理)

质数筛法:

列一张表能够窥见,每四个非质数x都是被(x/x的最小质因子)那几个数筛掉的。

nprime[1]=1;
for(i=2;i<=n;i++)
{
    if(!nprime[i])    prime[++len]=i;
    printf("%d: ",i);
    for(j=1;j<=len&&i*prime[j]<=n;j++)
    {
        nprime[i*prime[j]]=1;
        printf("%d ",i*prime[j]);
        if(i%prime[j]==0)    break;
    }
    puts("");
}

2: 4
3: 6 9
4: 8
5: 10 15 25
6: 12
7: 14 21 35 49
8: 16
9: 18 27
10: 20
11: 22 33
12: 24
13: 26 39
14: 28
15: 30 45
16: 32
17: 34
18: 36
19: 38
20: 40
21: 42
22: 44
23: 46
24: 48
25: 50

调节跟踪一下就足以领略那个break的法则。

譬如当i=12时,第1回筛掉24。分明,24的最小质因子是2,24/2=12。之后察觉12是2的翻番,表达12乘贰个2上述的质数,得到的合数的最小质因子都以2,就不应该由12来筛掉。

欧拉函数:$φ(n)$表示小于等于n且与n互质的平头个数。定义$φ(1)=1$。

显然,设$n=p1^a1*p2^a2*…*pk^ak$(正是把n分解质因数),那么小于n且不与n互质的整数,一定是集合$\{p1,p2,..,pk\}$中有个别数的积。

也便是说,$φ(n)$就是

欧拉函数定义&基础求法&筛法:http://www.cnblogs.com/linyujun/p/5194170.html

筛法补充表达:对于每一个质数p,欧拉函数值肯定12分p-1。对于每五个合数a,用筛掉它的数b的函数值来计量它的函数值。

几本性子的补充表达:

这几个注解没有仔细看是还是不是对的

(以下内容仅留作记录)

欧拉函数,用φ(n)表示

欧拉函数是求小于等于n的数中与n互质的数的数据

辣么,怎么求哩?~(~o ̄▽ ̄)~o

能够先在1到n-第11中学找到与n不互质的数,然后把他们减掉

比如φ(12)

把12质因数分解,12=2*2*3,其实就是收获了2和3四个质因数

然后把2的倍数和3的倍数都删掉

2的倍数:2,4,6,8,10,12

3的倍数:3,6,9,12

当然想一贯用12 – 12/2 – 12/3

但是6和12再度减了

为此还要把就是2的倍数又是3的倍数的数加回来 (>﹏<)

因而这么写12 – 12/2 – 12/3 + 12/(2*3)

那叫什么,这叫容斥啊,容斥定理听过呢

比如φ(30),30 = 2*3*5

所以φ(30) = 30 – 30/2 – 30/3 – 30/5 + 30/(2*3) + 30/(2*5) +
30/(3*5) – 30/(2*3*5)

只是容斥写起来好费劲( ̄. ̄)

有一种简易的方法

φ(12)   =   12*(1 – 1/2)*(1 – 1/3)                 =   12*(1 – 1/2 –
1/3 + 1/6)

φ(30)   =   30*(1 – 1/2)*(1 – 1/3)*(1 – 1/5)   =   30*(1 – 1/2 – 1/3

  • 1/5 + 1/6 + 1/10 + 1/15 – 1/30)

你看( •̀∀•́ ),拆开后发觉它帮您活动帮您容斥好

从而φ(30)的计量办法正是先找30的质因数

分别是2,3,5

然后用30* 1/2 * 2/3 * 十分八就解决了

附带一提,phi(1) = 1

代码如下:

710官方网站 1

 1 //欧拉函数
 2 int phi(int x){
 3     int ans = x;
 4     for(int i = 2; i*i <= x; i++){
 5         if(x % i == 0){
 6             ans = ans / i * (i-1);
 7             while(x % i == 0) x /= i;
 8         }
 9     }
10     if(x > 1) ans = ans / x * (x-1);
11     return ans;
12 }

710官方网站 2

(phi就是φ的读音)

敏感的代码,机智的自个儿(。・`ω´・)

本条的复杂度是O(√n),如果要你求n个数的欧拉函数,复杂度是O(n√n),这也太慢了

有更快的方式

跟埃筛素数大约

710官方网站 3

 1 #include<cstdio>
 2 const int N = 100000 + 5;
 3 int phi[N];
 4 void Euler(){
 5     phi[1] = 1;
 6     for(int i = 2; i < N; i ++){
 7         if(!phi[i]){
 8             for(int j = i; j < N; j += i){
 9                 if(!phi[j]) phi[j] = j;
10                 phi[j] = phi[j] / i * (i-1);
11             }
12         }
13     }
14 }
15 int main(){
16     Euler();
17 }

710官方网站 4

(Euler正是欧拉)

另一种,比地点更快的法门

内需运用如下性质

p为质数

  1. phi(p)=p-1  
    因为质数p除了1以外的因数只有p,故1至p的整数只有p与p不互质 

  2. 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p         (笔者不会申明)

3.若i mod p ≠0,  那么 phi( i * p )=phi(i) * ( p-1 )   (作者不会表明)

(所以小编说笔者会评释都是骗人的╮( ̄▽ ̄)╭)

代码如下:

710官方网站 5

 1 #include<cstdio>
 2 using namespace std;
 3 const int N = 1e6+10 ;
 4 int phi[N], prime[N];
 5 int tot;//tot计数,表示prime[N]中有多少质数 
 6 void Euler(){
 7     phi[1] = 1;
 8     for(int i = 2; i < N; i ++){
 9         if(!phi[i]){
10             phi[i] = i-1;
11             prime[tot ++] = i;
12         }
13         for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
14             if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
15             else{
16                 phi[i * prime[j] ] = phi[i] * prime[j];
17                 break;
18             }
19         }
20     }
21 }
22  
23 int main(){
24     Euler();
25 }

710官方网站 6

最终说下

a^b % p  不等价  (a%p)^(b%p) % p

因为

a^φ(p) ≡ 1 (mod p)

所以

a^b % p  =  (a%p)^(b%φ(p)) % p

(欧拉函数前提是a和p互质)

710官方网站 7

如果p是质数

平昔用这些公式

710官方网站 8

乖巧的代码,机智的本人(。・`ω´・)

 ///////////////////////////////////////////////

2016年7月23号

本身的天哪,笔者又发现了3个新公式,貌似能够摆脱a和p互质的牢笼,让我们来定名为:超欧拉取模进化公式

 710官方网站 9

那是历史性的少时,老母再也不用为a和p不互质而担心了= =

#include<cstdio>
int phi[100100],prime[30000];//nprime[100100];
int n,len;
int main()
{
    int i,j;
    n=50;
    phi[1]=1;
    //nprime[1]=1;
    for(i=2;i<=n;i++)
    {
        //if(!nprime[i])
        if(!phi[i])
        {
            prime[++len]=i;
            phi[i]=i-1;
        }
        //printf("%d: ",i);
        for(j=1;j<=len&&i*prime[j]<=n;j++)
        {
            //nprime[i*prime[j]]=1;
            //printf("%d ",i*prime[j]);
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
        //puts("");
    }
    return 0;
}

鲜明以上措施是线性的。

再有二个不供给以此天性的章程,复杂度$O(nloglogn)$。正是基于定义,对于各样质数x(未被其余数更新过欧拉函数值),去革新具有其倍数的欧拉函数值(正是乘上(x-1)再除以x)。

for(i=2;i<=n;i++)
    if(!phi[i])
        for(j=i;j<=n;j+=i)
        {
            if(!phi[j])    phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
            //i和i-1必定互质,因此保证正确,这样避免乘法溢出
        }

欧拉函数的有个别属性&欧拉定理:http://www.cnblogs.com/handsomecui/p/4755455.html

欧拉定理正是$a^φ(p){\equiv}1(mod\,p)$,那么$a^φ(p)$就是a关于模p的乘法逆元。可以用高速幂算。

哪个人知的事物:http://blog.csdn.net/qq\_36808030/article/details/76687103

当p为质数时即为费马小定理。

3.线性递推1-n关于模M的乘法逆元

inv[i]表示i的乘法逆元。

设$t=M/i$,$k=M%i$

可得$M=i*t+k$

那么$-i*t{\equiv}k(mod\,M)$

由于$inv[i]*inv[k]{\equiv}inv[i]*inv[k](mod\,M)$

逐条相乘得$-i*inv[i]*t*inv[k]{\equiv}inv[i]*k*inv[k](mod\,M)$

(不掌握干什么同余式找不到两边同时乘相同数仍旧创立的性质…)

可得$-t*inv[k]{\equiv}inv[i](mod\,M)$

即$-(M/i)*inv[M\%i]{\equiv}inv[i]$

那么,$inv[i]$能够等于$-(M/i)*inv[M\%i]$。

如果$-(M/i)*inv[M\%i]$为负,则不方便人民群众计算。

改成$(M-M/i)*inv[M\%i]\%m$就能保险是小小的的或然的正整数。

(http://www.cnblogs.com/dupengcheng/p/5493401.html)

那时候还有个验证(未仔细看):http://blog.csdn.net/yukizzz/article/details/51105009

另:

有一个在求解一切除法取模难点时都足以行使的章程:

在求解除法取模难点$(a/b)\%m$时,我们能够转账为$(a \% (b * m))/b$。

来道模板

洛谷P3811

1.

  1 //O2卡过
  2 #pragma GCC optimize(2)
  3 #pragma GCC diagnostic error "-std=gnu++14"
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 namespace fastIO{
  9     #define BUF_SIZE 100005
 10     #define OUT_SIZE 100005
 11     #define ll long long
 12     //fread->read
 13     bool IOerror=0;
 14     inline char nc(){
 15         static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
 16         if (p1==pend){
 17             p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
 18             if (pend==p1){IOerror=1;return -1;}
 19             //{printf("IO error!\n");system("pause");for (;;);exit(0);}
 20         }
 21         return *p1++;
 22     }
 23     inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
 24     inline void read(int &x){
 25         bool sign=0; char ch=nc(); x=0;
 26         for (;blank(ch);ch=nc());
 27         if (IOerror)return;
 28         if (ch=='-')sign=1,ch=nc();
 29         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 30         if (sign)x=-x;
 31     }
 32     inline void read(ll &x){
 33         bool sign=0; char ch=nc(); x=0;
 34         for (;blank(ch);ch=nc());
 35         if (IOerror)return;
 36         if (ch=='-')sign=1,ch=nc();
 37         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 38         if (sign)x=-x;
 39     }
 40     inline void read(double &x){
 41         bool sign=0; char ch=nc(); x=0;
 42         for (;blank(ch);ch=nc());
 43         if (IOerror)return;
 44         if (ch=='-')sign=1,ch=nc();
 45         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 46         if (ch=='.'){
 47             double tmp=1; ch=nc();
 48             for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
 49         }
 50         if (sign)x=-x;
 51     }
 52     inline void read(char *s){
 53         char ch=nc();
 54         for (;blank(ch);ch=nc());
 55         if (IOerror)return;
 56         for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
 57         *s=0;
 58     }
 59     inline void read(char &c){
 60         for (c=nc();blank(c);c=nc());
 61         if (IOerror){c=-1;return;}
 62     }
 63     //getchar->read
 64     inline void read1(int &x){
 65         char ch;int bo=0;x=0;
 66         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 67         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 68         if (bo)x=-x;
 69     }
 70     inline void read1(ll &x){
 71         char ch;int bo=0;x=0;
 72         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 73         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 74         if (bo)x=-x;
 75     }
 76     inline void read1(double &x){
 77         char ch;int bo=0;x=0;
 78         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 79         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 80         if (ch=='.'){
 81             double tmp=1;
 82             for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
 83         }
 84         if (bo)x=-x;
 85     }
 86     inline void read1(char *s){
 87         char ch=getchar();
 88         for (;blank(ch);ch=getchar());
 89         for (;!blank(ch);ch=getchar())*s++=ch;
 90         *s=0;
 91     }
 92     inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
 93     //scanf->read
 94     inline void read2(int &x){scanf("%d",&x);}
 95     inline void read2(ll &x){
 96         //#ifdef _WIN32
 97         //    scanf("%I64d",&x);
 98         //#else
 99         //#ifdef __linux
100             scanf("%lld",&x);
101         //#else
102         //    puts("error:can??t recognize the system!");
103         //#endif
104         //#endif
105     }
106     inline void read2(double &x){scanf("%lf",&x);}
107     inline void read2(char *s){scanf("%s",s);}
108     inline void read2(char &c){scanf(" %c",&c);}
109     inline void readln2(char *s){gets(s);}
110     //fwrite->write
111     struct Ostream_fwrite{
112         char *buf,*p1,*pend;
113         Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
114         void out(char ch){
115             if (p1==pend){
116                 fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
117             }
118             *p1++=ch;
119         }
120         void print(int x){
121             static char s[15],*s1;s1=s;
122             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
123             while(x)*s1++=x%10+'0',x/=10;
124             while(s1--!=s)out(*s1);
125         }
126         void println(int x){
127             static char s[15],*s1;s1=s;
128             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
129             while(x)*s1++=x%10+'0',x/=10;
130             while(s1--!=s)out(*s1); out('\n');
131         }
132         void print(ll x){
133             static char s[25],*s1;s1=s;
134             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
135             while(x)*s1++=x%10+'0',x/=10;
136             while(s1--!=s)out(*s1);
137         }
138         void println(ll x){
139             static char s[25],*s1;s1=s;
140             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
141             while(x)*s1++=x%10+'0',x/=10;
142             while(s1--!=s)out(*s1); out('\n');
143         }
144         void print(double x,unsigned int y){
145             static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
146                 1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
147                 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
148             if (x<-1e-12)out('-'),x=-x;x*=mul[y];
149             ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
150             ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
151             if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
152         }
153         void println(double x,int y){print(x,y);out('\n');}
154         void print(char *s){while (*s)out(*s++);}
155         void println(char *s){while (*s)out(*s++);out('\n');}
156         void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
157         ~Ostream_fwrite(){flush();}
158     }Ostream;
159     inline void print(int x){Ostream.print(x);}
160     inline void println(int x){Ostream.println(x);}
161     inline void print(char x){Ostream.out(x);}
162     inline void println(char x){Ostream.out(x);Ostream.out('\n');}
163     inline void print(ll x){Ostream.print(x);}
164     inline void println(ll x){Ostream.println(x);}
165     inline void print(double x,int y){Ostream.print(x,y);}
166     inline void println(double x,int y){Ostream.println(x,y);}
167     inline void print(char *s){Ostream.print(s);}
168     inline void println(char *s){Ostream.println(s);}
169     inline void println(){Ostream.out('\n');}
170     inline void flush(){Ostream.flush();}
171     //puts->write
172     char Out[OUT_SIZE],*o=Out;
173     inline void print1(int x){
174         static char buf[15];
175         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
176         while(x)*p1++=x%10+'0',x/=10;
177         while(p1--!=buf)*o++=*p1;
178     }
179     inline void println1(int x){print1(x);*o++='\n';}
180     inline void print1(ll x){
181         static char buf[25];
182         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
183         while(x)*p1++=x%10+'0',x/=10;
184         while(p1--!=buf)*o++=*p1;
185     }
186     inline void println1(ll x){print1(x);*o++='\n';}
187     inline void print1(char c){*o++=c;}
188     inline void println1(char c){*o++=c;*o++='\n';}
189     inline void print1(char *s){while (*s)*o++=*s++;}
190     inline void println1(char *s){print1(s);*o++='\n';}
191     inline void println1(){*o++='\n';}
192     inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
193     struct puts_write{
194         ~puts_write(){flush1();}
195     }_puts;
196     inline void print2(int x){printf("%d",x);}
197     inline void println2(int x){printf("%d\n",x);}
198     inline void print2(char x){printf("%c",x);}
199     inline void println2(char x){printf("%c\n",x);}
200     inline void print2(ll x){
201         //#ifdef _WIN32
202         //    printf("%I64d",x);
203         //#else
204         //#ifdef __linux
205             printf("%lld",x);
206         //#else
207         //    puts("error:can't recognize the system!");
208         //#endif
209         //#endif
210     }
211     inline void println2(ll x){print2(x);printf("\n");}
212     inline void println2(){printf("\n");}
213     #undef ll
214     #undef OUT_SIZE
215     #undef BUF_SIZE
216 };
217 using namespace fastIO;
218 typedef long long LL;
219 LL x,y;
220 LL a,b,n;
221 LL exgcd(LL a,LL b)
222 {
223     if(b==0)
224     {
225         x=1;y=0;
226         return a;
227     }
228     else
229     {
230         LL t1=exgcd(b,a%b),t=x;
231         x=y;
232         y=t-a/b*y;
233         return t1;
234     }
235 }
236 int main()
237 {
238     read(n);read(b);
239     for(a=1;a<=n;a++)
240     if(exgcd(a,b)==1)
241     {
242         LL t1=floor(-(double)x/b)+1;
243         println(t1*b+x);
244     }
245     return 0;
246 }

2.

 1 //O2也救不了我
 2 #pragma GCC optimize(2)
 3 #include<cstdio>
 4 typedef long long LL;
 5 LL n,p;
 6 LL poww(LL a,LL b)
 7 {
 8     LL base=a,ans=1;
 9     while(b)
10     {
11         if(b&1)    ans=(ans*base)%p;
12         b>>=1;
13         base=(base*base)%p;
14     }
15     return ans;
16 }
17 int main()
18 {
19     LL i;
20     scanf("%lld%lld",&n,&p);
21     for(i=1;i<=n;i++)
22         printf("%lld\n",poww(i,p-2));
23     return 0;
24 }

3.

 1 #include<cstdio>
 2 typedef long long LL;
 3 LL inv[3001000],n,p;
 4 int main()
 5 {
 6     LL i;
 7     scanf("%lld%lld",&n,&p);
 8     inv[1]=1;
 9     printf("%lld\n",inv[1]);
10     for(i=2;i<=n;i++)
11     {
12         inv[i]=(p-p/i)*inv[p%i]%p;
13         printf("%lld\n",inv[i]);
14     }
15     return 0;
16 }

http://www.bkjia.com/cjjc/1231861.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1231861.htmlTechArticle乘法逆元(欧拉函数,欧拉定理,质数筛法),欧拉
如果$ax{\equiv}1(mod\,p)$,且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。
有一个难题…

算逆元的艺术

  • 举办欧几里得

以此情势足够便于明白,而且对于单个查找成效就如也还能够,比前面要介绍的
登时幂的法门超越50%要快(尤其对于\(\bmod
{p}\)相比较大的时候)。
这些就是选择拓欧求解 线性同余方程\(a*x
\equiv c (\bmod {b})\)
的\(c=1\)的情景。我们就足以转正为\(a*x + b*y = 1\)
求解那些方程的解。

代码相比较简单:

void exgcd (ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return ;
    }
    exgcd (b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - a / b * y;    
}
        ll x, y;
    exgcd (i, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x);
  • 快速幂

那一个做法要动用 费马小定理

若\(p\)为素数, class=”math inline”>\(a\)为正整数,且 class=”math inline”>\(a\)、 class=”math inline”>\(p\)互质。
则有\(a^{p-1} \equiv 1 (\bmod
{p})\)。

以此大家就足以窥见它这一个姿势右边刚好为1。

从而大家就能够放入原式,就能够博得:

\(a*x\equiv 1 (\bmod {b})\)

\(a*x\equiv a^{p-1} (\bmod {b})\)

\(x \equiv a^{p-2} (\bmod {b})\)

为此大家得以用高速幂来算出 \(a^{p-2} (\bmod
{b})\)的值,那几个数就是它的逆元了

代码也极粗略:

ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    while (power) {
        if (power & 1) ans = (ans * x) % mod;
        x = (x * x) % mod;
        power >>= 1;
    }
    return ans;
}
printf ("%lld\n", fpm(i, p-2, p) );
  • 线性算法

用以求一连串数字对于3个\(\bmod
p\)的逆元。洛谷P3811
只得用那种方法,其余算法都比这么些要求一串要慢。

率先大家有1个,\(1^{-1}\equiv 1(\bmod
p)\)
然后设\(p=k*i+r,r<i,1<i<p\),再将以此姿势放到\(\bmod {p}\)意义下就会获得:
\(k*i+r \equiv 0 (\bmod p)\)

下一场乘上\(i^{-1}\),\(r^{-1}\)就足以获取:

\(k*r^{-1}+i^{-1}\equiv 0 (\bmod
p)\)

\(i^{-1}\equiv -k*r^{-1} (\bmod
p)\)

\(i^{-1}\equiv -\lfloor \frac{p}{i}
\rfloor*(p \bmod i)^{-1} (\bmod p)\)

于是乎,我们就足以从前方推出当前的逆元了。代码也就两行:

    a[i] = - (p / i) * a[p % i];
    a[i] = (a[i] % p + p) % p;
  • 阶乘逆元\(O(n)\)求

证明:
\(inv[i+1]=\frac{1}{(i+1)!}\)

\(inv[i+1]*(i+1)=\frac{1}{i!}=inv[i]\)

于是我们得以求出\(n!\)的逆元,然后逆推,就能够求出\(1…n!\)全部的逆元了。

递推式为
\(inv[i+1]*(i+1)=inv[i]\)

想不到的事物:http://blog.csdn.net/qq_36808030/article/details/76687103

逆元,一般用于求\(\frac{a}{b} (\bmod
{p})\)。
那种事物,笔者看到都以至极懵的,原来平昔不打算去上学,可实际非常粗暴,
以致很频繁考试都很被动,我下定狠心学一学2333。

也正是说,$φ(n)$正是

for(i=2;i<=n;i++)
    if(!phi[i])
        for(j=i;j<=n;j+=i)
        {
            if(!phi[j])    phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
            //i和i-1必定互质,因此保证正确,这样避免乘法溢出
        }

(欧拉函数前提是a和p互质)

跟埃筛素数差不离

710官方网站 10😉

其一申明从未有过仔细看是还是不是对的

譬如说当i=12时,第三次筛掉24。显著,24的最小质因子是2,24/2=12。之后发现12是2的倍数,表明12乘1个2以上的质数,获得的合数的最小质因子都是2,就不应该由12来筛掉。

分别是2,3,5

a^b % p  不等价  (a%p)^(b%p) % p

如果p是质数

 1 //欧拉函数
 2 int phi(int x){
 3     int ans = x;
 4     for(int i = 2; i*i <= x; i++){
 5         if(x % i == 0){
 6             ans = ans / i * (i-1);
 7             while(x % i == 0) x /= i;
 8         }
 9     }
10     if(x > 1) ans = ans / x * (x-1);
11     return ans;
12 }

710官方网站 11😉

辣么,怎么求哩?~(~o ̄▽ ̄)~o

以此的复杂度是O(√n),如若要你求n个数的欧拉函数,复杂度是O(n√n),那也太慢了

$ax{\equiv}1(mod\,p)$,那么能够设$ax-1=p(-y)$,那么$ax+py=1=gcd(a,p)$,求解即可

当p为质数时即为费马小定理。此时$φ(p)=p-1$,$a^{φ(p)}{\equiv}a^{p-1}{\equiv}1(mod\,p)$,那么$a^{p-2}$便是a关于模p的乘法逆元

本来想直接用12 – 12/2 – 12/3

由于$inv[i]*inv[k]{\equiv}inv[i]*inv[k](mod\,M)$

1.恢弘欧几里得

有三个题目,在求解进度中有除法,答案非常大,须要最后答案对某数p取模。分明,由于除法的产出,每3次运算之后取模是不行的。(比如:求1*7/2,答案对5取模。如若每1次运算取模也正是7%5/2%5,会博得1,正确结果却是3)若是不想高精度把最后结果算出来再取模的话,有三个措施,正是把除以x转换为乘上x关于模p的乘法逆元。(事实上,乘法逆元应该视为线性同余方程的解也正是一些数而不是1个数,可是一般只必要使用任意三个(比如最小正整数解)就能不辱义务职责)

备受瞩目以上办法是线性的。

由此还要把便是2的翻番又是3的倍数的数加回来 (>﹏<)

3.线性递推1-n关于模M的乘法逆元

急需选用如下性质

另:

显然,设$n=p1^a1*p2^a2*…*pk^ak$(正是把n分解质因数),那么小于n且不与n互质的整数,一定是集合$\{p1,p2,..,pk\}$中部分数的积。

inv[i]代表i的乘法逆元。

即$-(M/i)*inv[M\%i]{\equiv}inv[i]$

(以下内容仅留作记录)

710官方网站 12😉

欧拉函数的局地质量&欧拉定理:http://www.cnblogs.com/handsomecui/p/4755455.html

a^b % p  =  (a%p)^(b%φ(p)) % p

(所以笔者说作者会注解都以骗人的╮( ̄▽ ̄)╭)

有一种简单的点子

质数筛法:

 1 #include<cstdio>
 2 const int N = 100000 + 5;
 3 int phi[N];
 4 void Euler(){
 5     phi[1] = 1;
 6     for(int i = 2; i < N; i ++){
 7         if(!phi[i]){
 8             for(int j = i; j < N; j += i){
 9                 if(!phi[j]) phi[j] = j;
10                 phi[j] = phi[j] / i * (i-1);
11             }
12         }
13     }
14 }
15 int main(){
16     Euler();
17 }

3的倍数:3,6,9,12

下一场把2的翻番和3的翻番都删掉

p为质数

3.若i mod p ≠0,  那么 phi( i * p )=phi(i) * ( p-1 )   (笔者不会评释)

710官方网站 13

a^φ(p) ≡ 1 (mod p)

然后用30* 1/2 * 2/3 * 百分之八十就搞定了

因为

改成$(M-M/i)*inv[M\%i]\%m$就能担保是非常小的可能的正整数。

而是6和12再次减了

(phi就是φ的读音)

欧拉函数是求小于等于n的数中与n互质的数的数额

欧拉函数:$φ(n)$表示小于等于n且与n互质的平头个数。定义$φ(1)=1$。

  • 1/5 + 1/6 + 1/10 + 1/15 – 1/30)

调剂跟踪一下就足以领略那个break的规律。

来道模板

设c是b关于模m的逆元,即$b*c{\equiv}1(mod\,m)$,那么有$a/b{\equiv}(a/b)*1{\equiv}(a/b)*b*c{\equiv}a*c(mod\,m)$

欧拉定理做法正是当a,p互质时,$a^{φ(p)}{\710官方网站,equiv}1(mod\,p)$,那么$a^{φ(p)-1}$就是a关于模p的乘法逆元。能够用高速幂算。

有三个在求解一切除法取模难题(不用互质)时都能够动用的措施:

710官方网站 14😉

求法:

比如φ(12)

机智的代码,机智的本身(。・`ω´・)

还有个:http://blog.miskcoo.com/2014/09/linear-find-all-invert

2016年7月23号

  1. phi(p)=p-1  
    因为质数p除了1以外的因数只有p,故1至p的平头只有p与p不互质 

  2. 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p    
        (笔者不会注解)

为此这么写12 – 12/2 – 12/3 + 12/(2*3)

设$t=M/i$,$k=M%i$

 710官方网站 15

在求解除法取模难点$(a/b)\%m$时,我们能够转账为$(a \% (b * m))/b$。

代码如下:

φ(12)   =   12*(1 – 1/2)*(1 – 1/3)                 =   12*(1 – 1/2 –
1/3 + 1/6)

逐一相乘得$-i*inv[i]*t*inv[k]{\equiv}inv[i]*k*inv[k](mod\,M)$

欧拉函数定义&基础求法&筛法:http://www.cnblogs.com/linyujun/p/5194170.html

另一种,比地方更快的法子

(http://www.cnblogs.com/dupengcheng/p/5493401.html)

有更快的点子

能够先在1到n-第11中学找到与n不互质的数,然后把她们减掉

那是历史性的一刻,母亲再也不用为a和p不互质而揪心了= =

可得$-t*inv[k]{\equiv}inv[i](mod\,M)$

欧拉函数,用φ(n)表示

1.

代码如下:

本人的天哪,我又发现了二个新公式,貌似可以摆脱a和p互质的约束,让大家来定名为:超欧拉取模进化公式

比如φ(30),30 = 2*3*5

直接用这一个公式

只顾:break那里不能够是(!i%prime[j])!!!!!假设如此写一定要写成(!(i%prime[j]))!!感叹号先行级高!!

筛法补充表明:对于每3个质数p,欧拉函数值肯定十分p-1。对于每四个合数a,用筛掉它的数b的函数值来测算它的函数值。

3.

 1 //O2也救不了我
 2 #pragma GCC optimize(2)
 3 #include<cstdio>
 4 typedef long long LL;
 5 LL n,p;
 6 LL poww(LL a,LL b)
 7 {
 8     LL base=a,ans=1;
 9     while(b)
10     {
11         if(b&1)    ans=(ans*base)%p;
12         b>>=1;
13         base=(base*base)%p;
14     }
15     return ans;
16 }
17 int main()
18 {
19     LL i;
20     scanf("%lld%lld",&n,&p);
21     for(i=1;i<=n;i++)
22         printf("%lld\n",poww(i,p-2));
23     return 0;
24 }

干什么能如此做

那叫什么,那叫容斥啊,容斥定理听过呢

顺手一提,phi(1) = 1

  1 //O2卡过
  2 #pragma GCC optimize(2)
  3 #pragma GCC diagnostic error "-std=gnu++14"
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 namespace fastIO{
  9     #define BUF_SIZE 100005
 10     #define OUT_SIZE 100005
 11     #define ll long long
 12     //fread->read
 13     bool IOerror=0;
 14     inline char nc(){
 15         static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
 16         if (p1==pend){
 17             p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
 18             if (pend==p1){IOerror=1;return -1;}
 19             //{printf("IO error!\n");system("pause");for (;;);exit(0);}
 20         }
 21         return *p1++;
 22     }
 23     inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
 24     inline void read(int &x){
 25         bool sign=0; char ch=nc(); x=0;
 26         for (;blank(ch);ch=nc());
 27         if (IOerror)return;
 28         if (ch=='-')sign=1,ch=nc();
 29         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 30         if (sign)x=-x;
 31     }
 32     inline void read(ll &x){
 33         bool sign=0; char ch=nc(); x=0;
 34         for (;blank(ch);ch=nc());
 35         if (IOerror)return;
 36         if (ch=='-')sign=1,ch=nc();
 37         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 38         if (sign)x=-x;
 39     }
 40     inline void read(double &x){
 41         bool sign=0; char ch=nc(); x=0;
 42         for (;blank(ch);ch=nc());
 43         if (IOerror)return;
 44         if (ch=='-')sign=1,ch=nc();
 45         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
 46         if (ch=='.'){
 47             double tmp=1; ch=nc();
 48             for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
 49         }
 50         if (sign)x=-x;
 51     }
 52     inline void read(char *s){
 53         char ch=nc();
 54         for (;blank(ch);ch=nc());
 55         if (IOerror)return;
 56         for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
 57         *s=0;
 58     }
 59     inline void read(char &c){
 60         for (c=nc();blank(c);c=nc());
 61         if (IOerror){c=-1;return;}
 62     }
 63     //getchar->read
 64     inline void read1(int &x){
 65         char ch;int bo=0;x=0;
 66         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 67         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 68         if (bo)x=-x;
 69     }
 70     inline void read1(ll &x){
 71         char ch;int bo=0;x=0;
 72         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 73         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 74         if (bo)x=-x;
 75     }
 76     inline void read1(double &x){
 77         char ch;int bo=0;x=0;
 78         for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
 79         for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
 80         if (ch=='.'){
 81             double tmp=1;
 82             for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
 83         }
 84         if (bo)x=-x;
 85     }
 86     inline void read1(char *s){
 87         char ch=getchar();
 88         for (;blank(ch);ch=getchar());
 89         for (;!blank(ch);ch=getchar())*s++=ch;
 90         *s=0;
 91     }
 92     inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
 93     //scanf->read
 94     inline void read2(int &x){scanf("%d",&x);}
 95     inline void read2(ll &x){
 96         //#ifdef _WIN32
 97         //    scanf("%I64d",&x);
 98         //#else
 99         //#ifdef __linux
100             scanf("%lld",&x);
101         //#else
102         //    puts("error:can??t recognize the system!");
103         //#endif
104         //#endif
105     }
106     inline void read2(double &x){scanf("%lf",&x);}
107     inline void read2(char *s){scanf("%s",s);}
108     inline void read2(char &c){scanf(" %c",&c);}
109     inline void readln2(char *s){gets(s);}
110     //fwrite->write
111     struct Ostream_fwrite{
112         char *buf,*p1,*pend;
113         Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
114         void out(char ch){
115             if (p1==pend){
116                 fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
117             }
118             *p1++=ch;
119         }
120         void print(int x){
121             static char s[15],*s1;s1=s;
122             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
123             while(x)*s1++=x%10+'0',x/=10;
124             while(s1--!=s)out(*s1);
125         }
126         void println(int x){
127             static char s[15],*s1;s1=s;
128             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
129             while(x)*s1++=x%10+'0',x/=10;
130             while(s1--!=s)out(*s1); out('\n');
131         }
132         void print(ll x){
133             static char s[25],*s1;s1=s;
134             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
135             while(x)*s1++=x%10+'0',x/=10;
136             while(s1--!=s)out(*s1);
137         }
138         void println(ll x){
139             static char s[25],*s1;s1=s;
140             if (!x)*s1++='0';if (x<0)out('-'),x=-x;
141             while(x)*s1++=x%10+'0',x/=10;
142             while(s1--!=s)out(*s1); out('\n');
143         }
144         void print(double x,unsigned int y){
145             static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
146                 1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
147                 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
148             if (x<-1e-12)out('-'),x=-x;x*=mul[y];
149             ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
150             ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
151             if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
152         }
153         void println(double x,int y){print(x,y);out('\n');}
154         void print(char *s){while (*s)out(*s++);}
155         void println(char *s){while (*s)out(*s++);out('\n');}
156         void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
157         ~Ostream_fwrite(){flush();}
158     }Ostream;
159     inline void print(int x){Ostream.print(x);}
160     inline void println(int x){Ostream.println(x);}
161     inline void print(char x){Ostream.out(x);}
162     inline void println(char x){Ostream.out(x);Ostream.out('\n');}
163     inline void print(ll x){Ostream.print(x);}
164     inline void println(ll x){Ostream.println(x);}
165     inline void print(double x,int y){Ostream.print(x,y);}
166     inline void println(double x,int y){Ostream.println(x,y);}
167     inline void print(char *s){Ostream.print(s);}
168     inline void println(char *s){Ostream.println(s);}
169     inline void println(){Ostream.out('\n');}
170     inline void flush(){Ostream.flush();}
171     //puts->write
172     char Out[OUT_SIZE],*o=Out;
173     inline void print1(int x){
174         static char buf[15];
175         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
176         while(x)*p1++=x%10+'0',x/=10;
177         while(p1--!=buf)*o++=*p1;
178     }
179     inline void println1(int x){print1(x);*o++='\n';}
180     inline void print1(ll x){
181         static char buf[25];
182         char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
183         while(x)*p1++=x%10+'0',x/=10;
184         while(p1--!=buf)*o++=*p1;
185     }
186     inline void println1(ll x){print1(x);*o++='\n';}
187     inline void print1(char c){*o++=c;}
188     inline void println1(char c){*o++=c;*o++='\n';}
189     inline void print1(char *s){while (*s)*o++=*s++;}
190     inline void println1(char *s){print1(s);*o++='\n';}
191     inline void println1(){*o++='\n';}
192     inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
193     struct puts_write{
194         ~puts_write(){flush1();}
195     }_puts;
196     inline void print2(int x){printf("%d",x);}
197     inline void println2(int x){printf("%d\n",x);}
198     inline void print2(char x){printf("%c",x);}
199     inline void println2(char x){printf("%c\n",x);}
200     inline void print2(ll x){
201         //#ifdef _WIN32
202         //    printf("%I64d",x);
203         //#else
204         //#ifdef __linux
205             printf("%lld",x);
206         //#else
207         //    puts("error:can't recognize the system!");
208         //#endif
209         //#endif
210     }
211     inline void println2(ll x){print2(x);printf("\n");}
212     inline void println2(){printf("\n");}
213     #undef ll
214     #undef OUT_SIZE
215     #undef BUF_SIZE
216 };
217 using namespace fastIO;
218 typedef long long LL;
219 LL x,y;
220 LL a,b,n;
221 LL exgcd(LL a,LL b)
222 {
223     if(b==0)
224     {
225         x=1;y=0;
226         return a;
227     }
228     else
229     {
230         LL t1=exgcd(b,a%b),t=x;
231         x=y;
232         y=t-a/b*y;
233         return t1;
234     }
235 }
236 int main()
237 {
238     read(n);read(b);
239     for(a=1;a<=n;a++)
240     if(exgcd(a,b)==1)
241     {
242         LL t1=floor(-(double)x/b)+1;
243         println(t1*b+x);
244     }
245     return 0;
246 }

由此φ(30)的乘除办法正是先找30的质因数

nprime[1]=1;
for(i=2;i<=n;i++)
{
    if(!nprime[i])    prime[++len]=i;
    printf("%d: ",i);
    for(j=1;j<=len&&i*prime[j]<=n;j++)
    {
        nprime[i*prime[j]]=1;
        printf("%d ",i*prime[j]);
        if(i%prime[j]==0)    break;
    }
    puts("");
}

2: 4
3: 6 9
4: 8
5: 10 15 25
6: 12
7: 14 21 35 49
8: 16
9: 18 27
10: 20
11: 22 33
12: 24
13: 26 39
14: 28
15: 30 45
16: 32
17: 34
18: 36
19: 38
20: 40
21: 42
22: 44
23: 46
24: 48
25: 50

如果$-(M/i)*inv[M\%i]$为负,则不便宜总计。

欧拉函数exthttps://zhuanlan.zhihu.com/p/24902174

710官方网站 16

所以

再有1个不须求以此天性的法子,复杂度$O(nloglogn)$。正是依据定义,对于每种质数x(未被别的数更新过欧拉函数值),去革新具有其倍数的欧拉函数值(便是乘上(x-1)再除以x)。

 1 #include<cstdio>
 2 using namespace std;
 3 const int N = 1e6+10 ;
 4 int phi[N], prime[N];
 5 int tot;//tot计数,表示prime[N]中有多少质数 
 6 void Euler(){
 7     phi[1] = 1;
 8     for(int i = 2; i < N; i ++){
 9         if(!phi[i]){
10             phi[i] = i-1;
11             prime[tot ++] = i;
12         }
13         for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
14             if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
15             else{
16                 phi[i * prime[j] ] = phi[i] * prime[j];
17                 break;
18             }
19         }
20     }
21 }
22  
23 int main(){
24     Euler();
25 }

(不了解为何同余式找不到两边同时乘相同数依然成立的性质…)

710官方网站 17😉

那么$-i*t{\equiv}k(mod\,M)$

2.欧拉定理(费马小定理)

710官方网站 18😉

2.

末段说下

只是容斥写起来好坚苦( ̄. ̄)

您看( •̀∀•́ ),拆开后意识它帮你活动帮您容斥好

可得$M=i*t+k$

 1 #include<cstdio>
 2 typedef long long LL;
 3 LL inv[3001000],n,p;
 4 int main()
 5 {
 6     LL i;
 7     scanf("%lld%lld",&n,&p);
 8     inv[1]=1;
 9     printf("%lld\n",inv[1]);
10     for(i=2;i<=n;i++)
11     {
12         inv[i]=(p-p/i)*inv[p%i]%p;
13         printf("%lld\n",inv[i]);
14     }
15     return 0;
16 }

多少个属性的互补表明:

洛谷P3811

把12质因数分解,12=2*2*3,其实就是获取了2和3多少个质因数

那时还有个注脚(未仔细看):http://blog.csdn.net/yukizzz/article/details/51105009

φ(30)   =   30*(1 – 1/2)*(1 – 1/3)*(1 – 1/5)   =   30*(1 – 1/2 – 1/3

所以φ(30) = 30 – 30/2 – 30/3 – 30/5 + 30/(2*3) + 30/(2*5) +
30/(3*5) – 30/(2*3*5)

2的倍数:2,4,6,8,10,12

(Euler便是欧拉)

如果$ax{\equiv}1(mod\,p)$,且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。(不互质则乘法逆元不存在)

列一张表能够窥见,每贰个非质数x都以被(x/x的最小质因子)那个数筛掉的。

#include<cstdio>
int phi[100100],prime[30000];//nprime[100100];
int n,len;
int main()
{
    int i,j;
    n=50;
    phi[1]=1;
    //nprime[1]=1;
    for(i=2;i<=n;i++)
    {
        //if(!nprime[i])
        if(!phi[i])
        {
            prime[++len]=i;
            phi[i]=i-1;
        }
        //printf("%d: ",i);
        for(j=1;j<=len&&i*prime[j]<=n;j++)
        {
            //nprime[i*prime[j]]=1;
            //printf("%d ",i*prime[j]);
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
        //puts("");
    }
    return 0;
}

乖巧的代码,机智的自家(。・`ω´・)

 ///////////////////////////////////////////////

相关文章