本文主要是介绍数论模板(转载)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://blog.csdn.net/weixin_43238423/article/details/99685883
这位同学总结得挺好的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000007;
const ll N=100010;
ll v[N],prime[N],phi[N],v1[N],miu[N],m;
struct mat {ll d[5010][5010];int row,col;
};
inline mat Matrix_add (mat a,mat b){mat c;for(int i=1;i<=a.row;i++)for(int j=1;j<=a.col;j++){c.d[i][j]=a.d[i][j]+b.d[i][j];}return c;
}
inline mat Matrix_mul (mat a,mat b){mat c;memset(c.d,0,sizeof(c.d));for(int i=1;i<=a.row;++i)for(int j=1;j<=b.col;++j)for(int l=1;l<=a.col;++l)c.d[i][j]=(c.d[i][j]+a.d[i][l]*b.d[l][j]);return c;
}
inline mat Matrix_power (mat a,ll b,ll n){mat unit ;for(int i=1;i<=n;i++)unit.d[i][i]=1;unit.row=unit.col=a.row;for(;b;b>>=1){if(b&1)unit=Matrix_mul(unit,a);a=Matrix_mul(a,a);}return unit;
}
inline void primes_euler (ll n){memset(v,0,sizeof(v));m=0;for(int i=2;i<=n;i++){if(v[i]==0){v[i]=i;prime[++m]=i;phi[i]=i-1;}for(int j=1;j<=m;j++){if(prime[j]>v[i]||prime[j]>n/i)break;v[i*prime[j]]=prime[j];phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);}}
}
inline ll power (ll a,ll b ,ll p){ll ans=1;for(;b;b>>=1){if(b&1)ans=(ll)ans*a%p;a=(ll)a*a%p;}return ans;
}
inline ll exgcd (ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,x,y);ll z=x;x=y;y=z-(a/b)*y;return d;
}
inline ll C (ll n,ll m,ll mod){if(n<m)return 0;if(n==m)return 1;m=min(m,n-m);ll ans=1,fz=1,fm=1;for(ll i=1; i<=m; i++){fz=fz*(n+1-i)%mod;fm=fm*i%mod;}ans=(fz*power(fm,mod-2,mod))%mod;return ans;
}
inline ll Lucas (ll n,ll m,ll p){ll ans=1;while(n&&m&&ans){(ans*=C(n%p,m%p,p));n/=p;m/=p;}return ans;
}
inline ll baby_step_giant_step (ll a,ll b,ll p){map<ll,ll>m;m.clear();b%=p;ll t=(ll)sqrt(p)+1;for(ll j=0;j<t;j++){ll val =(ll)b*power(a,j,p)%p;m[val]=j;}a=power(a,t,p);if(a==0)return b==0?1:-1;for(ll i=0;i<=t;i++){ll val=power(a,i,p);ll j=m.find(val)==m.end()?-1:m[val];if(j>=0&&i*t-j>=0)return i*t-j;}return -1;
}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}
inline void mobius (ll n){for(int i=1;i<=n;i++){miu[i]=1,v1[i]=0;}for(int i=2;i<=n;i++){if(v[i])continue;miu[i]=-1;for(int j=2*i;j<=n;j+=i){v[j]=1;if((j/i)%i==0)miu[j]=0;else miu[j]*=-1;}}
}
inline ll phii (ll n){if(n==1)return 0;int ans=n;for(int i=2;i<=n;i++){if(n%i==0){ans=ans/i*(i-1);while(n%i==0)n/=i;}}if(n>1)ans/n*(n-1);return ans;
}
int main(){return 0;
}
这篇关于数论模板(转载)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
