则称a关于模p的乘法逆元为x,则称a关于模p的乘法逆元为x

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

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

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

有二个题材,在求解进程中有除法,答案很大,要求最后答案对某数p取模。明显,由于除法的产出,每两次运算之后取模是没用的。(比如:求1*7/2,答案对5取模。假使每回运算取模也等于7%5/2%5,会获取1,正确结果却是3)假如不想高精度把最终结果算出来再取模的话,有1个艺术,就是把除以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时,第四回筛掉24。分明,24的最小质因子是2,24/2=12。之后察觉12是2的翻番,说明12乘1个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,欧拉函数值肯定极度p-1。对于每一个合数a,用筛掉它的数b的函数值来总结它的函数值。

多少个属性的增补表明:

其一注脚没有仔细看是或不是对的

(以下内容仅留作记录)

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

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

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

可以先在1到n-1中找到与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 * 4/5就化解了

顺手一提,phi(1) = 1

代码如下:

图片 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 }

图片 2

(phi就是φ的读音)

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

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

有更快的措施

跟埃筛素数大概

图片 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 }

图片 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 )   (作者不会表明)

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

代码如下:

图片 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 }

图片 6

说到底说下

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

因为

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

所以

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

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

图片 7

如果p是质数

直白用这几个公式

图片 8

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

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

2016年7月23号

自个儿的天哪,作者又发现了贰个新公式,貌似可以摆脱a和p互质的自律,让我们来命名为:超欧拉取模进化公式

 图片 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;
}

无不侧目以上措施是线性的。

再有2个不要求以此天性的艺术,复杂度$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。
有七个题材…

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

有贰个标题,在求解进程中有除法,答案很大,必要最终答案对某数p取模。明显,由于除法的出现,每便运算之后取模是无济于事的。(比如:求1*7/2,答案对5取模。即便每三次运算取模也等于7%5/2%5,会获取1,正确结果却是3)倘使不想高精度把最后结出算出来再取模的话,有二个艺术,就是把除以x转换为乘上x关于模p的乘法逆元。(事实上,乘法逆元应该视为线性同余方程的解相当于部分数而不是二个数,可是一般只需要利用任意一个(比如最小正整数解)就能不负众望职分)

有多个题目,在求解进度中有除法,答案很大,需求最后答案对某数p取模。显著,由于除法的出现,每几次运算之后取模是不著见效的。(比如:求1*7/2,答案对5取模。如果每两遍运算取模也等于7%5/2%5,会赢得1,正确结果却是3)倘使不想高精度把最终结果算出来再取模的话,有几个主意,就是把除以x转换为乘上x关于模p的乘法逆元。(事实上,乘法逆元应该视为线性同余方程的解也等于一些数而不是一个数,但是一般只须要使用任意2个(比如最小正整数解)就能到位职责)

缘何能如此做

为何能那样做

设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)$

设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.增添欧几里得

1.恢弘欧几里得

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

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

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

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

质数筛法:

质数筛法:

列一张表可以发现,每1个非质数x都以被(x/x的最小质因子)那个数筛掉的。

列一张表能够发现,每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%prime[j])!!!!!若是那样写一定要写成(!(i%prime[j]))!!感叹号先行级高!!

调剂跟踪一下就足以精通那么些break的规律。

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

譬如当i=12时,首次筛掉24。明显,24的最小质因子是2,24/2=12。之后察觉12是2的倍数,表达12乘三个2上述的质数,得到的合数的最小质因子都以2,就不应当由12来筛掉。

调剂跟踪一下就可以知晓那么些break的原理。

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

比如当i=12时,第三遍筛掉24。分明,24的最小质因子是2,24/2=12。之后发现12是2的翻番,表达12乘二个2之上的质数,得到的合数的最小质因子都以2,就不应有由12来筛掉。

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

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

相当于说,$φ(n)$就是

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

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

相当于说,$φ(n)$就是

筛法补充表明:对于每1个质数p,欧拉函数值肯定卓殊p-1。对于每二个合数a,用筛掉它的数b的函数值来总括它的函数值。

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

几个天性的补充表明:

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

这一个注解平素不仔细看是否对的

筛法补充说明:对于每三个质数p,欧拉函数值肯定分外p-1。对于各个合数a,用筛掉它的数b的函数值来总括它的函数值。

(以下内容仅留作记录)

多少个性子的补偿表明:

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

那一个讲明不曾仔细看是否对的

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

(以下内容仅留作记录)

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

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

可以先在1到n-1中找到与n不互质的数,然后把她们减掉

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

比如φ(12)

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

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

可以先在1到n-1中找到与n不互质的数,然后把她们减掉

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

比如φ(12)

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

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

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

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

自然想平素用12 – 12/2 – 12/3

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

可是6和12再一次减了

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

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

自然想一直用12 – 12/2 – 12/3

从而这样写12 – 12/2 – 12/3 + 12/(2*3)

只是6和12重新减了

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

因而还要把即是2的翻番又是3的翻番的数加回来 (>﹏<)

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

据此那样写12 – 12/2 – 12/3 + 12/(2*3)

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

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

可是容斥写起来好辛勤( ̄. ̄)

比如φ(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)

φ(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

由此φ(30)的盘算情势就是先找30的质因数

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

分别是2,3,5

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

然后用30* 1/2 * 2/3 * 4/5就消除了

为此φ(30)的揣度办法就是先找30的质因数

顺便一提,phi(1) = 1

分别是2,3,5

代码如下:

然后用30* 1/2 * 2/3 * 4/5就化解了

图片 10😉

附带一提,phi(1) = 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 }

代码如下:

图片 11😉

图片 12😉

(phi就是φ的读音)

 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 }

灵活的代码,机智的我(。・`ω´・)

图片 13😉

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

(phi就是φ的读音)

有更快的章程

灵活的代码,机智的自家(。・`ω´・)

跟埃筛素数差不离

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

图片 14😉

有更快的章程

 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 }

跟埃筛素数几乎

图片 15😉

图片 16😉

(Euler就是欧拉)

 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 }

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

图片 17😉

内需采取如下性质

(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 )   (作者不会注解)

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 )   (作者不会注明)

图片 18😉

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

 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 }

代码如下:

图片 19😉

图片 20😉

终极说下

 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 }

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

图片 21😉

因为

说到底说下

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

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

所以

因为

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

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

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

所以

图片 22

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

如果p是质数

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

直接用这几个公式

图片 23

图片 24

如果p是质数

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

直白用那几个公式

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

图片 25

2016年7月23号

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

自家的天哪,作者又发现了2个新公式,貌似可以摆脱a和p互质的束缚,让我们来定名为:超欧拉取模进化公式

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

 图片 26

2016年7月23号

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

本人的天哪,小编又发现了1个新公式,貌似可以摆脱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;
}

 图片 27

明朗以上措施是线性的。

那是历史性的说话,大妈再也不用为a和p不互质而揪心了= =

还有1个不须求以此特性的点子,复杂度$O(nloglogn)$。就是依照定义,对于每一种质数x(未被此外数更新过欧拉函数值),去立异具有其倍数的欧拉函数值(就是乘上(x-1)再除以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;
}
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

再有壹个不需要那么些本性的章程,复杂度$O(nloglogn)$。就是依据定义,对于每一个质数x(未被其它数更新过欧拉函数值),去立异具有其倍数的欧拉函数值(就是乘上(x-1)再除以x)。

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

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://blog.csdn.net/qq_36808030/article/details/76687103

欧拉函数的片段性质&欧拉定理:http://www.cnblogs.com/handsomecui/p/4755455.html

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

欧拉定理做法就是当a,p互质时,$a^{φ(p)}{\equiv}1(mod\,p)$,那么$a^{φ(p)-1}$就是a关于模p的乘法逆元。可以用很快幂算。

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

意料之外的事物:http://blog.csdn.net/qq_36808030/article/details/76687103

inv[i]意味着i的乘法逆元。

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

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

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

可得$M=i*t+k$

inv[i]意味着i的乘法逆元。

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

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

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

可得$M=i*t+k$

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

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

(不知情怎么同余式找不到两边同时乘相同数还是创造的性质…)

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

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

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

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

(不精通干什么同余式找不到两边同时乘相同数照旧创建的性质…)

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

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

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

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

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

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

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

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

那会儿还有个表明(未仔细看):http://blog.csdn.net/yukizzz/article/details/51105009

改成$(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$。

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

来道模板

另:

洛谷P3811

有二个在求解一切除法取模难点(不用互质)时都可以利用的点子:

1.

在求解除法取模难题$(a/b)\%m$时,大家能够转化为$(a \% (b * m))/b$。

  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.

洛谷P3811

 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 }

1.

3.

  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 }
 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 }

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 }

相关文章