デジタルモデリング-C++実装
4005 ワード
数論
最大公約数(GCD)/最小公倍数(LCM)
素数判断及び打表
高速べき乗/乗算型
ユークリッドを広げる
乗算の逆元を求める
中国の残りの定理(一元線形同余方程式のグループを解く)
方程式ax=b(modn)を解く
モビウス関数の解
くみあわせすうかい
最大公約数(GCD)/最小公倍数(LCM)
/* */
int gcd(int a,int b)
{
if(0==b) return a;
while(b>0)
{
int temp=a%b;
a=b;
b=temp;
}
return a;
//while(b^=a^=b^=a%=b)
}
/* */
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
/* */
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
素数判断及び打表
/* n 1, 0*/
int IsPrime(int n)
{
if(n==2) return 1;
if(n%2==0||n<2) return 0;
int l=sqrt(n+1);
for(int i=3;i<=l;i+=2)
if(n%i==0) return 0;
return 1;
}
/* */
/*primes[] [2,N] primes[0] 0 2*/
/*isprime[] */
const int maxn=1000007;
int primes[maxn];
int isprime[maxn];
void euler_sieve()
{
int tot=0;
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(int i=2;i<=maxn;i++)
{
if(isprime[i]) primes[tot++]=i;
for(int j=0;jmaxn) break;
isprime[i*primes[j]]=0;
if(i%primes[j]==0) break;
}
}
}
高速べき乗/乗算型
/* (a^b)%p*/
int quickpow(int a,int b,int p)
{
int ret=1;
a%=p;
while(b)
{
if(b&1) ret=(a*ret)%p;
a=(a*a)%p;
b>>=1;
}
return ret;
}
/* (a*b)%p*/
int quickmul(int a,int b,int p)
{
int ans=0;
while(b)
{
if(b&1) {b--;ans=(ans+a)%p;}
b>>=1;
a=(a+a)%p;
}
return ans;
}
ユークリッドを広げる
/* ax+by=1*/
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
乗算の逆元を求める
/* ( ) ax=1(modb) -> ax-1=by -> ax+by=1*/
int modinverse(int a,int b)
{
int x,y;
int d=exgcd(a,b,x,y);
return d==1?(x%b+b)%b:-1;
}
中国の残りの定理(一元線形同余方程式のグループを解く)
/* ( ) x=a(modm)*/
/* ai,Mi ,ti Mi mi */
/*ans(ai*ti*Mi)*/
/*a[],p[] ,n, */
int crt(int a[],int p[],int n)
{
int muls=1;
int ret=0;
for(int i=0;ia[0]?a[0]:-1;
}
int x,y,d;
for(int i=1;i
方程式ax=b(modn)を解く
/* ax=b(modn), gcd(a,n), x vector<>*/
verctor lmodeq(int a,int b,int n)
{
int x,y;
int d=exgcd(a,n,x,y);
vector ans;
ans.clear();
if(b%d==0)
{
x=(x%n+n)%n;
x%=(n/d);
ans.push_back(x*(b/d)%(n/d));
for(int i=1;i
モビウス関数の解
/* mu
mu={
1 ,u=1
(-1)^k , k
0 ,u
}
*/
int Mobius(int n)
{
int cnt,k=0;
for(int i=2;i*i<=n;i++)
{
if(n%i) continue;
cnt=0;
k++;
while(n%i==0)
{
n/=i;
cnt++;
}
if(cnt>=2) return 0;
}
if(n) k++;
return k%2?-1:1;
}
くみあわせすうかい
/* : mod , . mod lucas*/
/* */
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
int fac(int n,int p)
{
int sum=1;
for(int i=1;i<=n;i++)
{
sum=(num*i)%p;
}
return sum;
}
int comb(int n,int m,int p)
{
int a=fac(m)*fac(n-m)%p;
int x,y;
exgcd(a,p,x,y);
return ((fac(n)*x)%p+p)%p;
}
/*Lucas */
int Lucas(int n,int m,int p)
{
if(m==0) return 1;
return comb(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
/* c(n,m)*/
int initcomb()
{
for(int i=0;i