一些数论的板子

1.线性筛逆元

1 for(ll i=2;i<=n;i++)
2         inv[i]=(mod-mod/i)*inv[mod%i]%mod;

2.快速乘

1 return ((a*b-(ll)(long double)a/p*b+1e-8)*p+p)%p;

3.excrt

 1 namespace excrt{
 2 ll ans=0,M=1;
 3 int insert(ll A,ll B)
 4 {
 5     ll a=A,b=B,c=(a-ans%b+b)%b,x,y;
 6     ll g=exgcd(M,b,x,y);
 7     ll bg=b/g;
 8     //if(c%g!=0) return -1;
 9     x=qadd(x,c/g,bg);
10     ans+=x*M,M*=bg,ans=(ans%M+M)%M;
11     return 1;
12 }
13 };

4.exlucas

 1 namespace exlucas{
 2 ll ans=0,M=1;
 3 ll son[10],pw[10];
 4 int num;
 5 int excrt_ins(ll A,ll B)
 6 {
 7     ll a=A,b=B,c=(a-ans%b+b)%b,x,y;
 8     ll g=exgcd(M,b,x,y);ll bg=b/g;
 9     if(c%g!=0) return -1;
10     x=qmul(x,c/g,bg);
11     ans+=x*M,M*=bg,ans=(ans%M+M)%M;
12     return 1;
13 }
14 ll get_mul(ll n,ll p,ll &sum,const ll &mo,int type)
15 {
16     if(n==0) return 1;
17     ll ans=1;
18     for(int i=2;i<=min(n,mo);i++)
19         if(i%p) ans=ans*i%mo;
20     ans=qpow(ans,n/mo,mo);
21     for(int i=2;i<=n%mo;i++)
22         if(i%p) ans=ans*i%mo;
23     sum+=1ll*(n/p)*type;
24     return ans*get_mul(n/p,p,sum,mo,type)%mo;
25 }
26 ll get_C(ll n,ll m,ll p,const ll &mo)
27 {
28     if(m>n) return 0;
29     ll sum=0;ll y;
30     ll nn=get_mul(n,p,sum,mo,1);
31     ll mm=get_mul(m,p,sum,mo,-1);
32     ll nm=get_mul(n-m,p,sum,mo,-1);
33     exgcd(mm,mo,mm,y);
34     mm=(mm%mo+mo)%mo;
35     exgcd(nm,mo,nm,y);
36     nm=(nm%mo+mo)%mo;
37     return nn*mm%mo*nm%mo*qpow(p,sum,mo)%mo;
38 }
39 ll C(ll n,ll m,const ll &mo)
40 {
41     if(m>n) return 0;
42     ll ret=0;
43     for(int i=0;i<num;i++){
44         ll val=get_C(n,m,son[i],pw[i]);
45         excrt_ins(val,pw[i]);
46     }
47     ret=ans,M=1,ans=0;
48     return ret;
49 }
50 };

5.杜教筛

  1 // luogu-judger-enable-o2
  2 #pragma GCC optimize(2)
  3 #pragma GCC optimize(3)
  4 #pragma GCC optimize"Ofast"
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <algorithm>
  8 #define NN 3001000
  9 #define MM 3000100
 10 #define maxn 3000000
 11 #define ll long long 
 12 #define uint unsigned int
 13 #define mod 1000000007
 14 using namespace std;
 15 
 16 int N,K,l,r,sq,len;
 17 namespace S1{
 18 int pr[NN],use[NN],mu[NN],phi[NN],smu[NN],cnt;
 19 ll sphi[NN];
 20 void Pre()
 21 {
 22     mu[1]=smu[1]=1,phi[1]=sphi[1]=1;
 23     for(int i=2;i<=maxn;i++)
 24     {
 25         if(!use[i]) pr[++cnt]=i,mu[i]=-1,phi[i]=i-1;
 26         smu[i]=smu[i-1]+mu[i],sphi[i]=sphi[i-1]+phi[i];
 27         for(int j=1;j<=cnt&&i*pr[j]<=maxn;j++){
 28             use[i*pr[j]]=1;
 29             if(i%pr[j]==0){
 30                 mu[i*pr[j]]=0;
 31                 phi[i*pr[j]]=phi[i]*pr[j];
 32                 break;
 33             }else{
 34                 mu[i*pr[j]]=-mu[i];
 35                 phi[i*pr[j]]=phi[i]*phi[pr[j]];
 36             }
 37         }
 38     }
 39 }
 40 };
 41 struct Chain{
 42     #define maxx 3000000
 43     int nxt[MM],head[MM],to[MM],cte;
 44     ll val[MM];
 45     void ae(int u,int v,ll w){
 46         cte++;to[cte]=v,val[cte]=w;
 47         nxt[cte]=head[u],head[u]=cte;
 48     }
 49     ll find(int U){
 50         int u=U%maxx;
 51         for(int j=head[u];j;j=nxt[j]){
 52             ll v=to[j];
 53             if(v==U) return val[j];
 54         }return -1;
 55     }
 56     void ins(int U,ll w){
 57         int u=U%maxx;
 58         ae(u,U,w);
 59     }
 60     #undef maxx
 61 }mu,phi;
 62 ll query_mu(int n)
 63 {
 64     if(n<=maxn) return S1::smu[n];
 65     ll ans;
 66     ans=mu.find(n);
 67     if(ans!=-1) return ans;
 68     ans=1;
 69     for(int i=2,la;i<=n;i=la+1){
 70         la=n/(n/i);
 71         ans-=1ll*(la-i+1)*query_mu(n/i);
 72     }mu.ins(n,ans);
 73     return ans;
 74 }
 75 ll query_phi(int n)
 76 {
 77     if(n<=maxn) return S1::sphi[n];
 78     ll ans;
 79     ans=phi.find(n);
 80     if(ans!=-1) return ans;
 81     ans=1ll*n*(n+1)/2;
 82     for(int i=2,la;i<=n;i=la+1){
 83         la=1ll*n/(n/i);
 84         ans-=1ll*(la-i+1)*query_phi(n/i);
 85     }phi.ins(n,ans);
 86     return ans;
 87 }
 88 
 89 int main()
 90 {
 91     //freopen("t1.in","r",stdin);
 92     int T;ll n;
 93     S1::Pre();
 94     scanf("%d",&T);
 95     while(T--){
 96         scanf("%lld",&n);
 97         ll ans_mu=query_mu(n);
 98         ll ans_phi=query_phi(n);
 99         printf("%lld %lld
",ans_phi,ans_mu);
100     }
101     return 0;
102 }

6.矩阵求逆
在当前矩阵右侧补上一个等大的单位矩阵，然后跑高斯消元，右侧剩下的矩阵就是逆矩阵

高斯消元的思想比较简单，每次把第$i$列中的某一行$j$上的数$a_{ji}$变成1，然后根据等式的性质，把第$j$行后面的元素都除以$a_{ji}$

然后再把这个等式带入到其他行中，设法把这些行第$i$列上的数消去，变成0，还要对右面的元素也进行修改，保证等式成立

如果任何一行的第$i$列都是0，说明该方程无解，即逆矩阵不存在

 1 struct M{
 2 ll f[NN][NN*2]; 
 3 int Gauss()
 4 {
 5     for(int i=1;i<=n;i++)
 6         f[i][i+n]=1;
 7     for(int i=1;i<=n;i++)
 8     {
 9         for(int j=i;j<=n;j++)
10         if(f[j][i]){
11             for(int k=1;k<=nn;k++)
12                 swap(f[i][k],f[j][k]);
13             break;
14         }
15         if(!f[i][i]) {return 0;}
16         ll inv,y;exgcd(f[i][i],mod,inv,y);
17         inv=(inv%mod+mod)%mod;
18         for(int j=i;j<=nn;j++)
19             f[i][j]=f[i][j]*inv%mod;
20         for(int j=1;j<=n;j++)
21         if(j!=i){
22             y=f[j][i];
23             for(int k=i;k<=nn;k++)
24                 f[j][k]=(f[j][k]-y*f[i][k]%mod+mod)%mod;
25         }
26     }return 1;
27 }
28 }m;