数学模板

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<string>
  7 #include<cmath>
  8 #include<ctime>
  9 #include<queue>
 10 #include<stack>
 11 #include<map>
 12 #include<set>
 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)
 14 #define re(i,l,r) for(int i=(l);i<=(r);i++)
 15 #define Clear(a,b) memset(a,b,sizeof(a))
 16 #define inout(x) printf("%d",(x))
 17 #define douin(x) scanf("%lf",&x)
 18 #define strin(x) scanf("%s",(x))
 19 #define LLin(x) scanf("%lld",&x)
 20 #define op operator
 21 #define CSC main
 22 typedef unsigned long long ULL;
 23 typedef const int cint;
 24 typedef long long LL;
 25 using namespace std;
 26 void inin(int &ret)
 27 {
 28     ret=0;int f=0;char ch=getchar();
 29     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=getchar();}
 30     while(ch>=‘0‘&&ch<=‘9‘)ret*=10,ret+=ch-‘0‘,ch=getchar();
 31     ret=f?-ret:ret;
 32 }
 33 namespace C
 34 {
 35     int c[1010][1010];
 36     void js1(int n)//Ñî»ÔÈý½Ç 
 37     {
 38         c[1][1]=1;
 39         re(i,1,n)
 40         {
 41             c[i][1]=i;
 42             re(j,2,i)c[i][j]=c[i-1][j-1]+c[i-1][j];
 43         }
 44     }
 45     void js2(int n,int k)//O(n)µÝÍÆ 
 46     {
 47         c[n][1]=n;
 48         re(i,2,n)c[n][i]=c[n][i-1]*(n-k+1)/k;
 49     }
 50 }
 51 namespace prime
 52 {
 53     int prime[100010],prime_tot;
 54     bool bo[1000010];
 55     void shai(int limit)//ÏßÐÔɸ 
 56     {
 57         re(i,2,limit)
 58         {
 59             if(!bo[i])prime[++prime_tot]=i;
 60             for(int j=1;j<=prime_tot&&i*prime[j]<=limit;j++)
 61             {
 62                 bo[i*prime[j]]=1;
 63                 if(i%prime[j]==0)break;
 64             }
 65         }
 66     }
 67     bool pd(int x)//ËØÊýÅж¨ 
 68     {
 69         shai(sqrt(x)+1);
 70         re(i,1,prime_tot)if(x%prime[i]==0)return 0;
 71         return 1;
 72     }
 73 }
 74 namespace nt
 75 {
 76     LL gcd(LL a,LL b){LL c;while(a%b)c=a%b,a=b,b=c;return b;}
 77     void exgcd(LL a,LL b,LL &d,LL &x,LL &y)//À©Õ¹Å·¼¸ÀïµÃ 
 78     {
 79         if(!b){d=a;x=1,y=0;}
 80         else exgcd(b,a%b,d,y,x),y-=x*(a/b);
 81     }
 82     LL qpow(LL a,LL b,LL mod)//¿ìËÙÃÝ 
 83     {
 84         a%=mod;LL ret=1;
 85         while(b)
 86         {
 87             if(b&1)ret=ret*a%mod;
 88             b>>=1;
 89             a=a*a%mod;
 90         }
 91         return ret;
 92     }
 93     LL PHI(LL x)//¼ÆËãµ¥¸öÊýµÄphi 
 94     {
 95         LL ret=x;
 96         for(LL i=2;i*i<=x;i++)if(x%i==0)
 97         {
 98             ret=ret-ret/i;
 99             while(x%i==0)x/=i;
100         }
101         if(x>1)
102         ret=ret-ret/x;
103         return ret;
104     }
105     int phi[1000010] ;
106     void shai(int limit)
107     {
108         phi[1]=1;
109         re(i,2,limit)if(!phi[i])
110             re(j,i,limit)
111             {
112                 if(!phi[j])phi[j]=j;
113                 phi[j]=phi[j]/i*(i-1);
114             }
115     }
116     LL inv1(LL a,LL n)//ÄæÔª(exgcd) 
117     {
118         LL d,x,y;
119         exgcd(a,n,d,x,y);
120         return d==1?(x+n)%n:-1;
121     }
122     LL inv2(LL a,LL n)//ÄæÔª(·ÑÂíС¶¨Àí) 
123     {
124         if(gcd(a,n)!=1)return -1;
125         LL zhi=PHI(n);
126         return qpow(a,zhi-1,n);
127     }
128     //x=a[i](mod m[i])(1<=i<=n)
129     LL china(int n,int *a,int *m)//ÖйúÊ£ÓඨÀí 
130     {
131         LL M=1,d,y,x=0;
132         re(i,1,n)M*=m[i];
133         re(i,1,n)
134         {
135             LL w=M/m[i];
136             exgcd(m[i],w,d,d,y);
137             x=(x+y*w*a[i])%M;
138         }
139         return (x+M)%M;
140     }
141     //½âÄ£·½³Ìa^x=b(mod n),nΪÖÊÊý
142     int log_mod(int a,int b,int n)//BSGS
143     {
144         int m,v,e=1;
145         m=(int)sqrt(n+1);
146         v=inv2(qpow(a,m,n),n);
147         map<int,int>x;
148         x[1]=0;
149         re(i,1,m-1)
150         {
151             e=e*a%n;
152             if(!x.count(e))x[e]=i;
153         }
154         re(i,0,m-1)
155         {
156             if(x.count(b))return i*m+x[b];
157             b=b*v%n;
158         }
159         return -1;
160     }
161     int prime[100010],prime_tot,mu[100010];
162     bool bo[100010];
163     void get_mu(int limit)//Ī±ÈÎÚ˹º¯Êý 
164     {
165         mu[1]=1;
166         re(i,2,limit)
167         {
168             if(!bo[i])prime[++prime_tot]=i,mu[i]=-1;
169             for(int j=1;j<=prime_tot&&i*prime[j]<=limit;j++)
170             {
171                 bo[i*prime[j]]=1;
172                 if(i%prime[j])mu[i*prime[j]]=-mu[i];
173                 else {mu[i*prime[j]]=0;break;}
174             }
175         }
176     }
177 }
178 int main()
179 {
180     return 0;
181 }