c++ strchr函数_strchr函数返回_模拟实现strchr函数(41)

int modular_linear_system(int b[],intw[],int k){

intd,x,y,a=0,m,n=1,i;

for(i=0;i<k;i)

n*=w[i];

for(i=0;i<k;i){

m=n/w[i];

d=ext_gcd(w[i],m,x,y);

a=(ay*m*b[i])%n;

}

return(an)%n;

}

//用素数表判定素数,先调用initprime

int plist[10000],pcount=0;

int prime(int n){

inti;

if((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))

return 0;

for(i=0;plist[i]*plist[i]<=n;i)

if (!(n%plist[i]))

return0;

returnn>1;

}

void initprime(){

inti;

for(plist[pcount]=2,i=3;i<50000;i)

if (prime(i))

plist[pcount]=i;

}

//miller rabin

//判断自然数n是否为素数

//time越高失败概率越低,一般取10到50

#include <stdlib.h>

#ifdef WIN32

typedef __int64 i64;

#else

typedef long long i64;

#endif

int modular_exponent(int a,int b,int n){//a^b mod n

intret;

for(;b;b>>=1,a=(int)((i64)a)*a%n)

if (b&1)

ret=(int)((i64)ret)*a%n;

returnret;

}

// Carmicheal number:561,41041,825265,321197185

int miller_rabin(int n,int time=10){

if(n==1||(n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))

return 0;

while(time--)

if(modular_exponent(((rand()&0x7fff<<16)rand()&0x7fffrand()&0x7fff)%(n-1)1,n-1,n)!=1)

return0;

return1;

}

int gcd(int a,int b){

returnb?gcd(b,a%b):a;

}

inline int lcm(int a,int b){

returna/gcd(a,b)*b;

}

//求1..n-1中与n互质的数的个数

int eular(int n){

intret=1,i;

for(i=2;i*i<=n;i)

if (n%i==0){

n/=i,ret*=i-1;

while(n%i==0)

n/=i,ret*=i;

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-34960-41.html